首页 > 试题广场 >

Perfect Sequence (25)

[编程题]Perfect Sequence (25)

热度指数：2946 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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.

输入描述:

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

输出描述:

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

示例1

输入

10 8<br/>2 3 20 4 5 1 6 7 8 9

输出

算法知识视频讲解

Python

初心者托奇

a = list(map(int,input().split()))
b = sorted(list(map(int,input().split())))
i,k = 0,1
while i + k < a[0]:
    if b[i] * a[1] >= b[i + k]:
        k += 1
    else:
        i += 1
print(k)

编辑于 2020-02-05 17:36:42 回复(0)