AtCoder AGC 011 A - Airport Bus (緑色, 300 点)

頭の整理がちょっと大変な問題

問題へのリンク

問題概要

人が次々とバス停に到着する ( 人の到着時刻が で与えられる)。以下の条件を満たすように乗客たちをバスに乗せていきたい。

• どの乗客もバス停に到着してから 分以内に出発させる
• 1 台のバスには 人までしか乗せられない

最小の何台のバスで全員を乗せることができるか求めよ。

制約

• 

考えたこと

問題で問われている状況を整理することが求められる。こういうのはまずは、色々な状況を想定してみるのがよいと思う。例えば...

• として最初の人が到着してから全員が 分以内に来るとしてもバス定員は 人なので、 人を運ぶには 台のバスが必要になる。

• でバス定員に余裕があっても、 で全員が 100 分起きに来るとしたら、1 人ずつしか乗せられないので 台のバスが必要になる。

こうしてみると、どちらの条件もよく効いてくることがわかる。しかしながら言えることは

---

先に到着した人を待たせてまで、後の人を先に乗せるメリットはまったくない

---

ということ。これは今回の問題では半ば当たり前だけど、今後より難しい問題で Greedy の考察をするときに大変重要になって来る考え方でもある。

解法を整理すると、

• 現在発車待ちのバスに、以下のいずれかの状態になるまでは、「来た人を乗せる」を繰り返す
  • 最初に人が乗ってから 分経つ
  • 乗客が 人になる
• 以上の状態になったら発車させて、その次の人が到着したと同時に新しいバスを開く

という風にすればよい。実装は

drken1215.hatenablog.com

に書いたような考え方でできる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, C, K; cin >> N >> C >> K;
    vector<int> T(N);
    for (int i = 0; i < N; ++i) cin >> T[i];
    sort(T.begin(), T.end());
    int res = 0;
    for (int i = 0; i < N;) {
        ++res;
        int start = i;
        while (i < N && T[i] - T[start] <= K && i - start < C) ++i;
    }
    cout << res << endl;
}