[AOJ] No. 0387 タクシー

2019年12月25日2020年12月18日

問題

方針

\( i \) 番目のタクシーは、\( i + 1 \) 番目以降のタクシー乗り場に行くことができるので、\( N \) 番目のタクシーから考えていきます。\( N \) 番目のタクシーは、\( s_N \) の最大値を取ることができます。\( s_N \) の最大値とは \( N \) 番目のタクシー乗り場の中で最大の料金のことです。\( N – 1 \) 番目のタクシーは、\( (s_{N-1}\) と \( s_{N}) \) の最大値を除いたものの中から、最大のものを取ることができます。例えば、\( s_{N} = 5, 6 \) のとき、\( N \) 番目のタクシーが \( 6 \) の値を取るので、\( s_N \) は空となり、\( N – 1\) 番目のタクシーは、\( 5 \) を取ることができませんが、先に \( N – 1 \) 番目のタクシーが \( 5 \) を取ることで、\( N \) 番目のタクシーが \( 6 \) を取ることができます。このような方針で実装します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    vector<ll> s[N];
    for (int i = 0; i < N; i++) {
        int M;
        cin >> M;
        for (int j = 0; j < M; j++) {
            int c;
            cin >> c;
            s[i].push_back(c);
        }
    }
    
    ll sum = 0;
    priority_queue<ll, vector<ll>> pq;
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < s[i].size(); j++) {
            pq.push(s[i][j]);
        }
        sum += pq.top();
        pq.pop();
    }
    
    cout << sum << "\n";
    return 0;
}