分数: 300 分
问题陈述
高桥是一家旅行社的导游。对于即将到来的巴士之旅, N 参与者已报名,每位参与者都有一个首选出发时间。
每位参与者的首选出发时间 i (1 \leq i \leq N) is T_i。根据旅行社的政策,为了有效运营旅游团,偏好出发时间相似的参与者会被集中在同一辆巴士上。具体来说,对于任意两个参与者 i, j 同一辆公交车上,他们的首选出发时间的绝对差异 |T_i - T_j| 最多必须 K。单辆巴士的乘坐人数没有上限。
高桥希望将每个参与者分配到一辆巴士上,并最大限度地减少所需的巴士数量。
找出将所有参与者分配到巴士所需的最少巴士数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 0 \leq T_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
输入
N K T_1 T_2 \ldots T_N
- 第一行包含 N,参与者数量,以及 K,同一巴士上参与者的首选出发时间允许的最大绝对差异,以空格分隔。
- 第二行包含首选出发时间 每个参与者的 T_1, T_2, \ldots, T_N ,以空格分隔。
输出
在一行上打印将所有参与者分配到总线所需的最小总线数。
示例输入 1
5 3 1 5 3 9 12
示例输出 1
3
示例输入 2
8 10 5 100 15 8 95 20 105 12
示例输出 2
3
示例输入 3
15 5 0 1 2 10 11 12 13 25 30 31 32 33 50 100 101
示例输出 3
6