点击链接PAT乙级-AC全解汇总

题目：
给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。

现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式：
输入第一行给出两个正整数 N 和 p，其中 N（≤10⁵）是输入的正整数的个数，p（≤10⁹）是给定的参数。第二行给出 N 个正整数，每个数不超过 10⁹​​​ 。

输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例：

10 8
2 3 20 4 5 1 6 7 8 9
1
2

输出样例：

8
1

我的代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;


int main()
{
    long long N,p;//如果不是longlong类型最后一个case会出错
    cin>>N>>p;
    int num[N];
    for(int i=0;i<N;i++)cin>>num[i];
    //从小到大排序
    sort(num,num+N);

///这是我原来的思路
//    //算一下，1.保留最小数需要删掉几个大数；2.保留最大数需要删掉几个小数；
//    //哪个需要删掉的数更多，就把这个数删掉
//    //直到最小数*p>=最大数结束，返回j-i+1
//    int i=0,j=N-1;
//    while(num[i]*pi)
//    {
//        //1.从小到大找第一个>num[i]*p的，(j-下标+1)为保留最小数需要删掉的数
//        int from_big=j;
//        while(num[from_big]>num[i]*p)from_big--;//需要删掉j-from_big个
//        //2.从小到大找第一个与p相乘>=end-1的，计数b，为保留最大数需要删掉的数
//        int from_small=i;
//        while(num[from_small]*p
//        //3.哪个需要删掉的数更多，就把这个数删掉(先不考虑一样多)
//        if(j-from_big>from_small-i) i++;
//        else j--;
//    }
//    cout<
///但是第四个case一直都是超时，随后参考了柳神的思路自己写的代码

    int result=0;
    for(int i=0;i<N;i++)
    {
        int j=i+result;
        while(j<N&&num[j]<=num[i]*p)j++;
        result=result>(j-i)?result:(j-i);//其实是j--,(j-i+1),正好抵消
    }
    cout<<result;

    return 0;
}

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

有的时候题目是一起做的，所以会有不需要的头文件