[AGC011A] Airport Bus
题意翻译
有$N$位乘客,第$i$位将在时刻$T_i$抵达机场。
你需要发出一些公交,将所有乘客从机场送到城市。如果一班公交在时刻$t$出发,那么所有满足$T_i\leq t\leq T_i+K$的乘客$i$可以坐上这一班公交。但是一班公交只能坐$C$人。
你可以在任意时刻发出公交(可以同时发车)求最少发车次数。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc011/tasks/agc011_a
高橋空港には,毎日飛行機で $ N $ 人の乗客が到着します. $ i $ 番目の乗客は時刻 $ T_i $ に到着します.
高橋空港に到着する乗客は全員バスで市内へ移動します.どのバスも定員は $ C $ 人であり,$ C $ 人以下の乗客を乗せることができます. 飛行機の乗客は,飛行機の到着時刻よりも早く出発するバスには乗ることができません. また,飛行機の到着時刻から $ K $ の時間が経過した後にもバスに乗れていないと,怒り出してしまいます. そのため,$ i $ 番目の乗客は,出発時刻が $ T_i $ 以上 $ T_i\ +\ K $ 以下であるようなバスに乗れるようにしないといけません.
この条件のもとで,うまくバスの出発時刻を定めるとき,必要なバスの数の最小値を求めてください. ただし,バスの出発時刻は必ずしも整数である必要はなく,同じ時刻に出発するバスが複数あってもかまいません.
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ C $ $ K $ $ T_1 $ $ T_2 $ $ : $ $ T_N $
输出格式
必要なバスの数の最小値を出力せよ.
输入输出样例
输入样例 #1
5 3 5
1
2
3
6
12
输出样例 #1
3
输入样例 #2
6 3 3
7
6
2
8
10
6
输出样例 #2
3
说明
### 制約
- $ 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 $ は整数
### Sample Explanation 1
例えば,時刻 $ 4.5 $, $ 6 $, $ 12 $ にバスを出発させ,次のように乗客をバスに乗せるとよいです. - 時刻 $ 4.5 $ に出発するバスには,時刻 $ 2,\ 3 $ に到着する乗客を乗せる. - 時刻 $ 6 $ に出発するバスには,時刻 $ 1,\ 6 $ に到着する乗客を乗せる. - 時刻 $ 12 $ に出発するバスには,時刻 $ 12 $ に到着する乗客を乗せる.