Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AGC011-A 「Airport Bus」 (300)

beta.atcoder.jp

概要

空港に N人の客がそれぞれ時刻 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

解説

1台のバスにはできるだけ定員ギリギリまで乗せたいが、待ち時間の制約上それができない場合がある。 そこで、「定員と待ち時間のどちらか一方をオーバーしかけたらバスを発車させる」という貪欲が考えられる。実はこれが正しい。

定員も待ち時間も余裕があるのにバスを発車させたとしよう。このとき1つ後のバスの先頭の人をこっちのバスに乗せてあげれば、1つ後のバスの制約がより緩くなる。というのも乗客数が1人減り、さらに1人目より2人目の方が到着時間が遅いからだ。

実装例

#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;
}

最初にlimit = -1としているのは、1人目のときだけ例外処理をするのを防ぐちょっとした技工である。

感想

  • 貪欲の中では見えやすく、確信の持ちやすい方だと思う。