Pat(A) 1085. Perfect Sequence (25)

原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1085

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

题目大意

给出N个数和一个参数P，选出一些数，使得这些数里的最大值M和最小值m满足M <= m * P，求出n的最大值，n是满足条件的序列中数字的个数。

解题报告

排序，然后i从0到N-1，依次寻找最大j，注意，由于找的最长的序列，故可以i进行变化使，j+1就行，使当前序列长度不变，节约时间。 需要注意的是： 1. 变量的类型啊，数据和P都是10^9的，int放不下。。

代码

#include "iostream" #include "algorithm" using namespace std; int N; long long P; long long data[100000 + 5]; int ans = 0; void init(){ int i; cin>>N>>P; for(i = 0; i < N; i++) cin>>data[i]; } void cal(){ int i,j; long long k; for(i = 0, j = 0; i < N,j < N; i++,j++){ k = data[i] * P; j = i + ans; while(j < N && data[j]<=k){ ans = max(ans,j-i+1); j++; } } } int main(){ init(); sort(data,data + N); cal(); cout<<ans<<endl; //system("pause"); }