1085. Perfect Sequence (25)

​ 时间限制

​ 300 ms

​ 内存限制

​ 65536 kB

​ 代码长度限制

​ 16000 B

​ 判题程序

​ Standard

​ 作者

​ CAO, Peng

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

两个点，1先排序，在循环2，注意二层循环不能直接+1，直接加一会有个测试点通不过，由于找最大个数，所以可以直接+max,这样便不会超时

代码如下：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


int main(){
	long long n,p;
	scanf("%lld%lld",&n,&p);
	vector<long long>v(n);
	for(int i=0;i<n;++i){
		scanf("%lld",&v[i]);
	}
	sort(v.begin(),v.end());
	int max=1;	
	int temp=0;
	for(int i=0;i<n;++i){
		for(int j=i+max;j<n;++j){
			if(v[j]<=v[i]*p){
				temp=j-i+1;
				if(temp>max){
					max=temp;
				}
			}else{
				break;
			}
		}
	}
	printf("%d",max);
	return 0;

}