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 9Sample Output:
8
将序列的左端固定，然后用二分法确定最长的序列的右端。然后对左端的进行循环，确定最长的序列。
1 #include <iostream> 2 #include <algorithm> 3 4 using namespace std; 5 6 long long sequence[100000]; 7 long long p; 8 9 int main() 10 { 11 long long n; 12 cin >> n >> p; 13 for (int i = 0; i < n; i++) 14 cin >> sequence[i]; 15 sort(sequence, sequence + n); 16 int maxLength = 0; 17 for (int i = 0; i < n; i++) 18 { 19 if (maxLength >= n - i) 20 break; 21 int left = i, right = n - 1; 22 if (sequence[i] * p >= sequence[right] && maxLength < n - i) 23 maxLength = n - i; 24 else 25 { 26 while (right - left != 1) 27 { 28 int middle = (left + right) / 2; 29 if (sequence[i] * p >= sequence[middle]) 30 left = middle; 31 else 32 right = middle; 33 } 34 if (right - i > maxLength) 35 maxLength = right - i; 36 } 37 } 38 cout << maxLength; 39 }
PAT 1085. Perfect Sequence (25)
原文：http://www.cnblogs.com/jackwang822/p/4737031.html