1085 Perfect Sequence (25 分)

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



注意点：1.int*int 的范围必须用long long;
　　　　2.if(a[n-1]<=x) return n;

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn =;

 int a[maxn];

 int n,p;

 int binary_Search(int i,long long x){

     if(a[n-]<=x)

         return n;

     int left=i+,right=n-;

     while(left<right){

         int mid = (left+right)/;

         if(a[mid]>x){

             right =mid;

         }else{

             left= mid+;

         }

     }

     return left;

 }

 int main(){

     cin>>n>>p;

     for(int i=;i<n;i++)

         cin>>a[i];

     sort(a,a+n);

     int ans=;

     for(int i=;i<n;i++){

     //    int j=binary_Search(i,(long long)a[i]*p);

         int j=upper_bound(a+i+,a+n,(long long)a[i]*p)-a;

         ans=max(ans,j-i);

     //    cout<<j<<" "<<i<<endl;

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

1085 Perfect Sequence (25 分)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

最新文章

热门文章