タクシー [パソコン甲子園2018 予選 H]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0387

考察過程

1. タクシーはタクシー乗り場を後ろにしか移動できないので、後ろのタクシーから客を確定させていく
2. どの客を乗せればいいかだけを決めれば、どのタクシーがどの客を乗せるかは適当に後から決められる
3. ということは貪欲に単価の高い客を載せていけば良さそう
4. priority_queueを使えば最も高い数から順番に得られる
5. この貪欲で本当にいいのか分からんけど、出すと通る

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0387/judge/3162210/C++14

貪欲法で解く。
後ろのタクシー乗り場から順に確定させていく。
貪欲法をするために、priority_queueを使って最大値を取得できるようにしておく。
　
i番目のタクシーを確定するために、i番目のタクシー乗り場の金額をpriority_queueに全部入れる。
そこから最大のものを取り出して、確定させる。
　
次に、i-1番目のタクシーを確定するために、i-1番目のタクシー乗り場の金額を追加でpriority_queueに全部入れる。
そこから最大のものを取り出して、確定させる。
　
これを繰り返していくと答え。
どのタクシーがどの客を乗せたかは問われていないため、これで問題ない。

int N;
int M[301010]; vector<int> C[301010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        cin >> M[i];
        rep(j, 0, M[i]) {
            int c; cin >> c;
            C[i].push_back(c);
        }
    }

    ll ans = 0;
    priority_queue<int> pq;
    rrep(i, N - 1, 0) {
        fore(c, C[i]) pq.push(c);

        ans += pq.top();
        pq.pop();
    }
    cout << ans << endl;
}