分数: 366 分
问题陈述
高桥正在果园帮忙收割苹果。果园有 N 苹果树排成一条直线,每棵树都种植在不同的位置。的 i- 第棵树位于坐标处 数轴上的 X_i 。
高桥使用收割车收集苹果。推车可以跨一段时间停放 [L, R] (L \leq R)在数轴上,他可以从该区间内的所有树上收获苹果。但是,小车可以覆盖的范围是有限制的:间隔的长度 R - L 最多必须是 K.
Takahashi 最多想选择单个长度区间 K 停放车并从尽可能多的树上收获苹果。
一棵树 i 在区间内 [L, R] 当且仅当 L \leq X_i \leq R.
确定可收获苹果的最大树数。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 0 \leq X_i \leq 10^9
- X_i \neq X_j (i \neq j)
- 所有输入均为整数
输入
N K X_1 X_2 \ldots X_N
- 第一行包含 N,苹果树的数量,以及 K,间隔长度的上限,以空格分隔。
- 第二行包含每棵苹果树的坐标 X_1, X_2, \ldots, X_N,用空格分隔。
输出
在单行上打印最多可收获的苹果树数量,间隔长度最多 K.
示例输入 1
5 3 1 5 2 8 4
示例输出 1
3
示例输入 2
8 10 3 15 7 25 12 30 8 20
示例输出 2
4
示例输入 3
12 100 50 200 75 300 120 80 450 90 500 110 85 95
示例输出 3
8