题目 完美数列

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

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

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

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

输入样例：

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

输出样例：

8

代码

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N, p; cin >> N >> p; vector <int> list; for (int i = 0; i < N; i++) { int temp; cin >> temp; list.push_back(temp); } sort(list.begin(), list.end()); // 按顺序排列 int prefect = 0; // 可以选择完美数列的最大个数 int j = 0; // 防止第四个测试点运行超时 for (int i = 0; i < N; i++) // 循环嵌套找到最大prefect { long long int mp = (long long)list[i] * p; if (list[N - 1]<=mp) // 最后一个数仍小于等于mp时，不用进入内层循环 { prefect = max(prefect, N - i); break; } for (j; j < N; j++) { if (list[j]>mp) { prefect = max(prefect, j - i); break; } } } cout << prefect; }

写这个题的时候思路不难，用了两个循环嵌套找最大的prefect，结果有两个测试点一直过不去，一个报运行超时，一个报答案错误。

测试点四那个运行超时把最后一个数的判断和break提前了一下，然后把内层循环改成每次从上一次循环的j之后开始就过了。

然后是测试点五的答案报错，发现是mp长度不够，万一两个$10^9$次方相乘超出了int存储范围。

一开始我把他定义成了long long int，然而还是报错，找了半天之后发现右端其实还是两个int相乘，得到的结果还是int，心情复杂，右边也给他来一下就过了。