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