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

题目描述：求完美数列，要求数列元素尽可能多。完美数列公式：M<=m*p，M为数列中最大值，m为数列中最小值，p是给定的值。

输入：第一行两个值n，p，分别为数列元素个数，p是给定的值；第二行n个值给出无序的数列。

输出：完美数列元素的个数。

解题思路：要用long long类型存值，不然测试点5报错。将给定的数列从小到大排序，接着从索引0开始遍历，用二分查找找到每个元素能组成的最大完美子序列长度，进行比较后得出结果。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200000+5;
long long v[maxn];
int n, p;
int search(int g){
	int l=g, r=n-1, mid;
	int tx = 0;
	while(l<=r){
		mid = (l+r)/2;
		if(v[mid]<=v[g]*p){
			tx = max(tx,mid-g+1);
			l = mid + 1;
		}
		else r = mid-1;
	}
	return tx;
}
int main()
{
	int ans=0;
	scanf("%d %d", &n, &p);
	for(int i=0; i<n; i++) scanf("%lld", &v[i]);
	sort(v,v+n);//小到大 
	for(int i=0; i<n; i++){
		ans = max(ans,search(i));
	}
	printf("%d", ans);
	return 0;
}