Python实现Pat 1085. Perfect Sequence (25)

左手的ㄟ右手 2022-06-04 06:53 149阅读 0赞

### [题目][Link 1] ###

Given a sequence of positive integers and another positive integer p. The sequence is said to be a “perfect sequence” if M <= m \* p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.

Output Specification:

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:  
10 8  
2 3 20 4 5 1 6 7 8 9  
Sample Output:  
8

### 解答 ###

排序题。

N,p = [int(x) for x in input().split(' ')]
    nums=[int(x) for x in input().split(' ')]
    nums.sort()
    low=0
    up=1
    maximum =1
    for low in range(N-1):
        while(up<N):
            if nums[up]<=nums[low]*p:
                up+=1
            elif up-low>maximum:
                maximum=up-low
            else:
                break
    print (maximum)

### 又有错误，懒得调试了。 ###

![这里写图片描述][SouthEast]

[Link 1]: https://www.patest.cn/contests/pat-a-practise/1085
[SouthEast]: /images/20220604/57aa3e39ff30471db0a85ec9f978d1ee.png

发表评论取消回复

表情：

评论列表（有 0 条评论，149人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT 甲级 1085 Perfect Sequence (25 分) +二分相关知识

1085 Perfect Sequence (25 分) Given a sequence of positive integers and another positi

超、凢脫俗/ 2024年02月19日 21:55/ 0 赞/ 43 阅读

相关 PAT (Advanced Level) Practice 1085 Perfect Sequence

最后一个测试点过不了，是因为m\p可能超过了int的范围，导致判断条件出错，所以将数据类型改成longlong就好了。 include <iostream>

ゞ浴缸里的玫瑰/ 2023年07月03日 07:25/ 0 赞/ 13 阅读

相关 Python实现Pat 1078. Hashing (25)

Pat 1078. Hashing (25) The task of this problem is simple: insert a sequence of disti

男娘i/ 2022年06月05日 06:56/ 0 赞/ 208 阅读

相关 Python实现Pat 1085. Perfect Sequence (25)

[题目][Link 1] Given a sequence of positive integers and another positive integer p. Th

左手的ㄟ右手/ 2022年06月04日 06:53/ 0 赞/ 150 阅读

相关 Python实现Pat 1032. Sharing (25)

[题目][Link 1] Given a collection of number segments, you are supposed to recover the s

谁践踏了优雅/ 2022年06月04日 06:49/ 0 赞/ 209 阅读

相关 Python实现Pat 1032. Sharing (25)

[题目传送门][Link 1] 解答 line0=input().split(' ') N=int(line0[2]) dic={}

朴灿烈づ我的快乐病毒、/ 2022年06月04日 06:20/ 0 赞/ 208 阅读

相关 1085. Perfect Sequence (25)

Given a sequence of positive integers and another positive integer p. The sequence is sa

àì夳堔傛蜴生んèń/ 2022年05月29日 14:16/ 0 赞/ 151 阅读

相关 1085. PAT单位排行 (25)

每次 PAT 考试结束后，考试中心都会发布一个考生单位排行榜。本题就请你实现这个功能。输入格式：输入第一行给出一个正整数N（<=105），即考生人数。随后N行，每行按下

末蓝、/ 2022年05月26日 10:00/ 0 赞/ 141 阅读

相关 PAT1085:Perfect Sequence

1085 Perfect Sequence （25 分） Given a sequence of positive integers and another positive

红太狼/ 2022年05月10日 14:28/ 0 赞/ 172 阅读

相关 (PAT) 1085 Perfect Sequence (Upper_Bound二分的使用)

Given a sequence of positive integers and another positive integer p. The sequence is sa

柔情只为你懂/ 2022年03月27日 11:14/ 0 赞/ 151 阅读