← 返回题目列表

AtCoder · awc0088_b

B. 巴士旅游团分部

中文机器翻译题面 查看原题

分数: 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