给定 n 个整数,从中选择若干个数,要求所选数的最大值与最小值之差不超过 d。求最多可以选择多少个数。
所选位置不要求在原序列中连续。相同数值的不同位置可以分别选取。
第一行输入两个整数 n,d。第二行输入 n 个整数 a_1,a_2,\ldots,a_n。
输出一个整数,表示最多可以选择的数的个数。
6 2 8 3 5 4 12 5
4
12 5 20 4 11 7 4 9 14 6 8 25 10 5
7
30 8 40 13 27 9 18 15 44 21 16 12 33 17 19 14 50 20 11 23 25 18 10 31 22 16 28 7 24 26 15 39
12
可以选择原序列第 2,3,4,6 个数,分别为 3,5,4,5。最大值与最小值之差为 5-3=2,共选出 4 个数。
两个 5 来自不同位置,可以同时选择。不能选出满足要求的 5 个数,因此答案为 4。
对于所有测试数据,保证:1\le n\le10^5,0\le d\le10^9,1\le a_i\le10^9。
本题共 10 个测试点,每个测试点 10 分,各测试点独立计分。
| 测试点编号 | n\le | 特殊性质 |
|---|---|---|
| 1 \sim 2 | 10 | 无 |
| 3 \sim 4 | 10^3 | 无 |
| 5 \sim 6 | 10^5 | A |
| 7 \sim 10 | 10^5 | 无 |
特殊性质 A:d=0。