给定一个正整数数列,和正整数 \(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
题解
如果用双层循环的话,肯定是会超时的。
需要先排序。再用滑动窗口(双指针)来解决此题。
不断移动右边界。然后用左边界向右移动不断试探。并记录最大值。
示例过程如下:
1、先升序排序
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 20 |
2、两个指针 \(left\) 和 \(right\) 指向第一个数据,最大长度 \(maxLen = 0\)
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 20 |
---|---|---|---|---|---|---|---|---|---|
\(left\) |