简答题
偏难
#13211
完美数列 给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M ≤ m*p,则称这个数列是完美数列。 现在给定参数 p 和一些正…
完美数列
给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M ≤ m*p,则称这个数列是完美数列。
现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。
时间限制:1000
内存限制:65536
输入
输入第一行给出两个正整数 n 和 p,其中 n(≤ 105)是输入的正整数的个数,p(≤ 109)是给定的参数。第二行给出 n 个正整数,每个数不超过 109。
输出
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
样例输入
10 8 2 3 20 4 5 1 6 7 8 9
样例输出
8
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, p;
cin >> n >> p;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
sort(nums.begin(), nums.end());
int max_len = 0;
for (int i = 0; i < n; ++i) {
long long target = (long long)nums[i] * p;
auto it = upper_bound(nums.begin() + i, nums.end(), target);
int cnt = it - (nums.begin() + i);
if (cnt > max_len) {
max_len = cnt;
}
}
cout << max_len << endl;
return 0;
}</pre>
这道题暂未补解析。