A - Airport Bus
概要
これから空港に $N$ 人の客が来る、 $i$ 番目の客は、今から $T_i$ 秒後に来る。
これらの客全員を、何台かのバスで運ばなければならない。
1 台のバスの定員は $C$ 人で、さらに客を到着から $K$ 秒より長く待たせることはできない。
客全員を運ぶのに必要な、最小のバスの台数を求めよ。
制約
- $2 \leq N \leq 10^5$
- $1 \leq C \leq 10^9$
- $1 \leq K \leq 10^9$
- $1 \leq T_i \leq 10^9$
解説
バスには詰められるだけ多くの客を詰めるのが最善である。下手に残しても得はしない。
したがって、「定員と待ち時間のどちらか一方をオーバーしかけたらバスを発車させる」という貪欲で解くことができる。
実装例
最初に limit = -1 としているのは、1 人目のときだけ例外処理をしなくて済むようにするためである。
提出 #3583053 - AtCoder Grand Contest 011
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;
int main() {
ll N, C, K;
cin >> N >> C >> K;
ll T[N];
for (int i = 0; i < N; ++i) {
cin >> T[i];
}
sort(T, T + N);
ll ans = 0, limit = -1, cap = 0;
// ans = 発車された累計バス台数
// limit = 先頭の客の許容時間
// cap = 今バスに乗ってる客数
for (int i = 0; i < N; ++i) {
if (cap == C || T[i] > limit) {
// 制限オーバーなので新しいバスに乗せる
++ans;
limit = T[i] + K;
cap = 0;
}
++cap;
}
cout << ans << endl;
return 0;
}
|