传送门
https://pintia.cn/problem-sets/994805260223102976/problems/994805291311284224
题目
给定一个正整数数列，和正整数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.首先将数字都读进数组里，然后用sort或者qsort排序（升序），都可以
2.接着就是比较绕的一个地方了，这里我的第一种方法的时间复杂度是m * n，然后有一个测试点超时了，考虑了一下是算法太麻烦。
这里给大家介绍一种很快速的算法，以本题样例为例：
对其排序后，是这样的：
下标：|00|01|02|03|04|05|06|07|08|09|
数值：|01|02|03|04|05|06|07|08|09|20|
1.首先用1 * 8 = 8，然后会对比到下标为7 的位置，并记长度为8。
2.接着就厉害了，按我之前的做法是从下标为01的地方对比，这样就麻烦了。
快速的做法是计算2 * 8 = 16，然后用下标为08的地方与其对比，发现符合，然后求出从下标01到08位置的长度，是8，不大于之前的长度，接着向后对比；用下标为09的数值与2 * 8 = 16对比，发现不符合规则，然后此次对比过程结束。
3.新的最大值是3 * 8 = 24，用下标为09的地方与其对比，发现符合，然后求从下标02到09的长度，是8，不大于之前的长度，并且发现已经全部对比完毕，所以结束。
源代码
//C/C++实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
long long p;
scanf("%d %d", &n, &p);
vector<int> v(n);
for(int i = 0; i < n; ++i){
scanf("%d", &v[i]);
}
sort(v.begin(), v.end());
int final_count = 0;
for(int i = 0; i < n; ++i){
long long max = v[i] * p;
for(int j = i + final_count; j < n; ++j){
if(v[j] <= max){
if(j - i + 1 > final_count){
final_count = j - i + 1; //从j到i的数值的数量
}
}
else{
break;
}
}
}
printf("%d\n", final_count);
return 0;
}
