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.

给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

Input Specification:

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

输入第一行给出两个正整数 N 和 p，其中 N（≤10^​5​​）是输入的正整数的个数，p（≤10​^9​​）是给定的参数。第二行给出 N 个正整数，每个数不超过 10^​9​​。

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

解题思路

1. 读入序列并储存；
2. 将其按照增序排列；
3. 从第一个元素开始遍历，对于每个元素通过二分法找到恰好大于需求值（p倍元素值）的位置（也可以使用upper_bound()函数）；
4. 计算其差值，并与当前最大距离比较以找出最大差值；
5. 计算当前位置可能达到的最大长度与目前最大差值进行对比，可以减少运算量；
6. 输出最大差值，并返回零值；

代码

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 100010
int main(){
    int N,p,a[maxn];
    int ans;
    int i,j;
    scanf("%d%d",&N,&p);
    for(i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+N);
    ans=1;
    for(i=0;i<N;i++){
        j=upper_bound(a+i+1,a+N,(long long)a[i]*p)-a;
        ans=max(ans,j-i);
        if(j>N-i){
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

运行结果