A1085 Perfect Sequence (25 point(s))

求M≤m×p最大长度M-m

1. 原文

原题

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

2. 解析

求M≤m×p M-m最大

数组排序，对于每个当前i 查找满足num[i]*p>=num[j]的最大j，j不回溯。记录最大j-i

3. AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
long long num[100010]={};
int main()
{
	int n;
	long long p;
	scanf("%d%lld",&n,&p);
	for (int i = 0; i < n; ++i)
	{
		scanf("%lld",&num[i]);
	}
	sort(num,num+n);
	int i=0;
	int j=0;
	int ans=-1;
	for (; i < n; ++i)
	{
		for (; j < n; ++j)
		{
			if (num[j]>num[i]*p)
			{
				break;
			}
		}
		if (j-i>ans)
		{
			ans=j-i;
		}
	}
	printf("%d\n", ans);
	return 0;
}