首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; int main() {     int n, p;     cin &gt;&gt; n &gt;&gt; p;     vector&lt;int&gt; nums(n);     for (int i = 0; i &lt; n; ++i) {         cin &gt;&gt; nums[i];     }     sort(nums.begin(), nums.end());     int max_len = 0;     for (int i = 0; i &lt; 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 &gt; max_len) {             max_len = cnt;         }     }     cout &lt;&lt; max_len &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。