← 返回题目列表

AtCoder · agc011_a

A. 机场巴士

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

分数: 300 点

问题陈述

每天, N 乘客抵达高桥机场。 的 i第 位乘客到达时间 T_i.

每位到达高桥机场的乘客都会乘坐巴士前往市区。每辆巴士最多可容纳 C 乘客。 当然,乘客不能乘坐早于飞机到达机场出发的巴士。 此外,如果乘客仍然无法乘坐公共汽车,他/她也会生气 K 飞机到达后的时间单位。 因此,有必要安排巴士,以便 i第一位乘客可以乘坐以下时间出发的巴士 T_i 和 T_i + K (含)。

在这种情况下设置公交车的发车时间时,求出最少需要的公交车数量。 这里,每辆公交车的发车时间不需要是整数,可能有多辆公交车同时出发。

约束

  • 2 \leq N \leq 100000
  • 1 \leq C \leq 10^9
  • 1 \leq K \leq 10^9
  • 1 \leq T_i \leq 10^9
  • C, K 和 T_i 是整数。

输入

输入由标准输入按以下格式给出:

N C K
T_1
T_2
:
T_N

输出

打印所需的最少巴士数量。


示例输入 1

5 3 5
1
2
3
6
12

示例输出 1

3

例如,以下三个总线就足够了:

  • 公交车准时出发 4.5,运载按时间到达的乘客 2 和 3.
  • 公交车准时出发 6,运载按时间到达的乘客 1 和 6.
  • 公交车准时出发 12,运载按时间到达的乘客 12.

示例输入 2

6 3 3
7
6
2
8
10
6

示例输出 2

3