Snack Shop 2

2 secs 1024 MB

それぞれの状況において、最も安いお菓子を買うのが最適なのは明らかですが、お菓子を買うたびに全てのお菓子の値段を調べていては計算量が $O(NK)$ となってしまい実行時間制限に間に合いません。
そこで、優先度付きキューなどのデータ構造を用いてお菓子の値段を管理することによってそれぞれの状況において最も安いお菓子の値段を $O(\log N)$ で取得することができ、全体で $O(N \log N)$ でこの問題を解くことができます。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, k;
    cin >> n >> k;

    priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<>> q;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        q.push(make_pair(a, b));
    }

    long long ans = 0;
    for(int i = 0; i < k; i++){
        pair<long long, long long> p = q.top();
        q.pop();
        ans += p.first;
        p.first += p.second;
        q.push(p);
    }
    cout << ans << endl;
}