P2949 [USACO09OPEN] Work Scheduling G 题解

题目描述

思路

我们第一步应该想到优先做截止时间靠前的任务，所以我们按截止时间从小到大为第一关键字，收益从大到小为第二关键字。

但是这个时候，有一类型的样例有可能会 hack 掉这个做法：

7
1 2
1 3
2 5
2 7
3 10
3 11
3 12

33

我们会发现我们可以舍弃所有的截止时间为第一天的任务，而去做第二天和第三天的。

所以我们可以想到要用反悔贪心。

我们先按之前的方法计算，当遇到没时间做却比之前选择要做的利益最小的任务的利益更大，那么我们用这个任务替换之前利益最小的任务。

至于如何获取利益最小的任务，我们可以用小根堆。

具体实现可以看代码。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
/*
7
1 2
1 3
2 5
2 7
3 10
3 11
3 12

33
---
7
1 2
1 3
2 5
2 7
10 10
10 11
10 12

45
*/
/*
从前往后，然后替换。
优先队列维护最小的，然后替换最小的。
*/
struct node{
    int d, p;
} a[1000005];
bool cmp(node x, node y) {
    if (x.d != y.d) return x.d < y.d;
    else return x.p > y.p;
}
int n, d[1000005], p[1000005], res;
priority_queue <int, vector<int>, greater<int> > q;
map <int, int> mp;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i].d >> a[i].p;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i ++) {
        if (a[i].d != a[i - 1].d) res += a[i].d - a[i - 1].d;
        if (res) {
            q.push(a[i].p);
            res --;
        }
        else if (q.top() < a[i].p) {
            q.pop();
            q.push(a[i].p);
        }
    }
    int ans = 0;
    while (q.size()) {
        ans += q.top();
        q.pop();
    }
    cout << ans;
    return 0;
}