题解 P1230 【智力大冲浪】

· · 题解

蜜汁贪心

怎么贪？贪几个亿？（我一分钱都不敢花，老秦人穷怕了）

如果截止时间靠前的先做，那样例顺序就是(1,30) (2,60) (3,40) (4,70) (4,50) (4,20) (6,10)，损失80，答案9920

如果罚款多的先做，样例顺序就是(4,70) (2,60) (4,50) (3,40) (1,30) (4,20) (6,10)，损失60，答案9940

说明这两种方法都！不！行！

我们可以这么思考：如果一个活动铁定超时，那么它无论什么时候完成，罚款都相等。所以，如果它超时，那就破罐子破摔，扔到最后做，这样就给其它要求限时完成的任务腾出时间。（发散思维：如果罚款数目和超时时间成正比，这题就不能用贪心了，而且至少是蓝题难度）

因此可以按照截止时间排序，然后按截止时间分配任务。如果截止时间t之前分配了超过t件任务，说明有铁定超时的任务了。我们需要放弃一些任务，显然，放弃罚款最小的几个是最优选择。

模拟一下我们的样例：

1: (1, 30)
2: (2, 60)
3: (3, 40)
4: (4, 70) (4, 50) (4, 20)
5: ∅
6: (6, 10)

t=4处多出两个任务，因此在t<=4范围内放弃两个任务，显然罚款最小的是(4, 20)和(1, 30)。其余的地方没有溢出的任务，因此最终损失是50，得到9950元。

根据描述，每次分配任务都要添加进任务队列，而放弃的时候删除罚款最小的，因此优先队列是不二选择。

这样，每个任务最多被放入优先队列一次，弹出一次，再加上预处理排序，总的时间复杂度为O(nlogn)。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef struct {
    int t;
    int f;
} game;
game arr[1000];

bool cmp(game a, game b) {
    return a.t < b.t;
}

priority_queue<int, vector<int>, greater<int> > q; // 注意是小顶堆

int main() {
    int m, n, i, t, ans = 0;
    scanf("%d %d", &m, &n);
    for (i = 0; i < n; i++) scanf("%d", &arr[i].t);
    for (i = 0; i < n; i++) scanf("%d", &arr[i].f);
    sort(arr, arr + n, cmp);
    t = arr[0].t;
    for (i = 0; i < n; i++) {
        if (arr[i].t > t) {
            while (q.size() > t) {
                ans += q.top();
                q.pop();
            }
            t = arr[i].t;
        }
        q.push(arr[i].f);
    }
    while (q.size() > t) {
        ans += q.top();
        q.pop();
    }
    printf("%d", m - ans);
    return 0;
}