PAT1085:Perfect Sequence

红太狼 2022-05-10 14:28 145阅读 0赞

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

思路:

利用二分查找法,在待查元素的右边查找符和要求的元素

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    const long MAXN = 100010;
    long long a[MAXN];
    long long p = 0;
    long n = 0;
    
    int binarySearch(int i, long long x) {
    	if (a[n - 1] <= x) {
    		return n;  //如果所有数字都小于的话,直接返回该数
    	}
    	int l = i + 1, r = n - 1;
    	int mid;
    	while (l < r) {
    		mid = (l + r) / 2;
    		if (a[mid] <= x) {
    			l = mid + 1;
    		}
    		else {
    			r = mid;
    		}
    	}
    	return l; //返回中间位置元素
    }
    
    
    int main() {
    	cin >> n;   //数字个数
    	cin >> p;   //待乘的数
    
    	for (long i = 0; i < n; ++i) {
    		cin >> a[i];   //输入数字
    	}
    	sort(a, a + n); //排序
    	
    	int ans = 0;
    	for (int i = 0; i < n; ++i) {
    		long long comp = a[i] * p;   
    		int j = binarySearch(i, comp);   //向右边二分查找最大的数
    		ans = max(ans, j - i);
    	}
    
    	cout << ans << endl;
    	
    	system("PAUSE");
    	return 0;
    }