1085. Perfect Sequence (25)

àì夳堔傛蜴生んèń 2022-05-29 14:16 125阅读 0赞

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:**

--------------------

题目大意：

代码：

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    long long a[100001],n;
    long long BinarySearch(long long start,long long end,long long key)
    {
        long long left=start,right=end;
        while(left<=right)
        {
            long long mind=left+(right-left)/2;
            if(a[mind]>key)
            {
                right=mind-1;
            }
            else if(a[mind]<key)
            {
                left=mind+1;
            }
            else
            {
                return mind;
            }
        }
        return left-1;
    }
    int main()
    {
        long long i,j,m,k,t,p;
        scanf("%lld %lld",&n,&p);
        for(i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
        }
        sort(a,a+n);
        k=0;
        for(i=0;i<n;i++)
        {
           m=a[i]*p;//int 会越界，所以用 long long（不然最后一个case通不过）
           t=BinarySearch(i,n-1,m);
           if(k<t-i+1)
           {
               k=t-i+1;
           }
        }
        printf("%lld\n",k);
        return 0;
    }