【題解】ZeroJudge a567: 死線排程

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a567
【解題想法】Greedy、排程問題

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

int n, a[10005], d[10005], p[10005];

bool cmp(int x, int y){
    return d[x] < d[y];
}

int main() {
    while (cin >> n){
        for (int i = 0; i < n; i++){
            a[i] = i;
            cin >> d[i] >> p[i];
        }
        sort(a, a+n, cmp);
        priority_queue <int, vector<int>, greater<int> > pq;
        int ans = 0;
        for (int i = 0; i < n; i++){
            if (d[a[i]] > pq.size()){
                ans += p[a[i]];
                pq.push(p[a[i]]);
            }
            else if (d[a[i]] == pq.size() && p[a[i]] > pq.top()){
                ans -= pq.top();
                pq.pop();
                ans += p[a[i]];
                pq.push(p[a[i]]);
            }
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends