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 (<= 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^.
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 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 bool cmp(const long int& a, const long int& b){return a<b;} 6 int main(){ 7 long int n, p, i, j; 8 cin>>n>>p; 9 vector<long int> v(n); 10 for(i=0; i<n; i++) scanf("%d", &v[i]); 11 sort(v.begin(), v.end(), cmp); 12 long int max=0; 13 for(i=0; i<n; i++){ 14 15 for( j=n-1; j>=i; j--){ 16 if(v[i]*p>=v[j]){ 17 if(max<j-i+1) max=j-i+1; 18 break; 19 } 20 } 21 if(v[i]*p>=v[n-1]&&max<j-i) max=j-i; 22 } 23 cout<<max<<endl; 24 return 0; 25 }
二分查找
1 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 bool cmp(const long int& a, const long int& b){return a<b;} 6 int main(){ 7 long int n, p, i, j， max=0; 8 cin>>n>>p; 9 vector<long int> v(n); 10 for(i=0; i<n; i++) scanf("%d", &v[i]); 11 sort(v.begin(), v.end(), cmp); 12 for(i=0; i<n; i++){ 13 int low=i, high=n-1; 14 while(low<=high){ 15 int mid=(low+high)/2; 16 if(v[i]*p<v[mid]) high=mid-1; 17 else if(v[i]*p>=v[mid]) low=mid+1; 18 if(max<mid-i+1 && v[i]*p>=v[mid]) max=mid-i+1; 19 } 20 } 21 cout<<max<<endl; 22 return 0; 23 }