1030. 完美数列(25)

发表于 | 分类于 ，

题目描述

给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。

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

输入格式：

输入第一行给出两个正整数N和p，其中N（<= 105）是输入的正整数的个数，p（<= 109）是给定的参数。第二行给出N个正整数，每个数不超过109。

输出格式：

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

输入样例：

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

输出样例：

8

提交代码

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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int n, i, j;
    int result = 0;
    long int p;
    
    scanf("%d %ld", &n, &p);
    vector<long int> vec(n);

    for (i = 0; i < vec.size(); i++) {
        scanf("%ld", &vec[i]);
    }
    sort(vec.begin(), vec.end());
    for (i = 0; i < vec.size(); i++) {
        for (j = i + result; j < vec.size(); j++) {
            if (vec[j] <= vec[i] * p) {
                result = j - i + 1 > result ? j - i + 1 : result;
            } else {
                break;
            }
        }
    }
    printf("%d\n", result);

    return 0;
}

个人思考

不知所措…… 代码基本照搬柳婼の代码。然后认真看了一下之前闻所未闻的two-pointer算法，结果发现好像接触过的快慢指针就是类似的东西。

第一次提交，只拿了两分，对照了一下代码，感觉“没什么问题啊”。然后把long int改成了跟她写的一样的long long。再提交，还是只拿了两分，挠头。要不把三目运算符给改回 if-else 语句？第三次提交，好，过了。然后以为是这俩之间的微妙差别，各种查资料，发现不是。最后反反复复对比，终于发现：

喵的一声哭了出来.jpg

参考资料