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放不下。。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#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");
}