给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。
现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
输入第一行给出两个正整数 N 和 p，其中 N（≤）是输入的正整数的个数，p（≤）是给定的参数。第二行给出 N 个正整数，每个数不超过 1。
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
10 8
2 3 20 4 5 1 6 7 8 9
8#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; const int maxn = 100010; long long s[maxn]; int main(){ int n, p, count=0, max = 0; scanf("%d%d", &n, &p); for (int i = 0; i<n; i++){ scanf("%d", &s[i]); } sort(s, s + n); int i, j; for (i = 0; i<n; i++){ for (j = i+max; j<n; j++){ if (s[j] <= s[i] * p){ count = j - i +1; if (count>max){ max = count; } } else break; } if (n - i <= max)break; } printf("%d", max); system("pause"); }
注意点：一开始从后往前遍历，超时了。正向遍历就可以直接从i+max位置开始，尽可能减少计算次数。但不知道为什么下面的代码有三个测试点不通过，感觉逻辑并没有错。
#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; const int maxn = 100010; long long s[maxn]; int main(){ int n, p, count=0, max = 0; scanf("%d%d", &n, &p); for (int i = 0; i<n; i++){ scanf("%d", &s[i]); } sort(s, s + n); int i, j; for (i = 0; i<n; i++){ for (j = i+max; j<n; j++){ if (s[j] > s[i] * p){ count = j - i; if (count>max){ max = count; } break; } } if (n - i < max)break; } printf("%d", max); system("pause"); }
ps:后面的方法直接判断s[j] >s[i] * p会出现一种情况就是后面的数没有一个满足大于这个条件，但都比这个数小，这时实际长度是在增加的，而只判断大于不会有效。
原文：https://www.cnblogs.com/tccbj/p/10363090.html