(PAT) 1085 Perfect Sequence (Upper_Bound二分的使用)

柔情只为你懂 2022-03-27 11:14 140阅读 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: ###

解题思路:

利用二分查找的思想,先将所有元素进行排序,然后从最小的元素开始遍历,利用upperbound查找第一个M 使M > m\*p

把每次查找的结果保存到一个数组中,最后选出最大的那个元素

注意,题目中给出的p是10的9次方,是比较大的元素,所以要用long long型保存,至于lower\_Bound,upper\_bound,套用模板即可

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int MAXN = 100010;
    int numbers[MAXN];
    int squences[MAXN];
    int N;
    int P;
    int lowerBound(int i,long long x) {
    	if (numbers[N - 1] <= x) return N;
    	int mid;
    	int left = i + 1, right = N - 1;   //
    	while (left < right) {
    		mid = left + (right - left) / 2;
    		if (numbers[N - 1] == numbers[mid] && numbers[mid] >  x) return 0;  //遍历到了最后一个
    		if (numbers[mid] > x ) {
    			right = mid;
    		}
    		else {
    			left = mid + 1;
    		}
    	}
    	return left;
    }
    bool cmp(int a,int b) {
    	return a > b;
    }
    int main() {
    	scanf("%d %d", &N, &P);
    	for (int i = 0; i < N; ++i) {
    		scanf("%d", &numbers[i]);
    	}
    	sort(numbers, numbers + N);
    	for (int i = 0; i < N; ++i) {
    		squences[i] = lowerBound(i, (long long)P*numbers[i]) - i;  //注意要转型!!!
    	}
    	sort(squences, squences + N, cmp);
    	printf("%d", squences[0]);
    	system("PAUSE");
    	return 0;
    }