【反悔贪心】P2949 Work Scheduling G 题解

今天遇到了一个很神奇的题目，就是能反悔的贪心。赶紧记录一下。

题面：Luogu - P2949

大体意思是：先把所有任务按照截止时间从小到大排序，然后枚举，遇到一个能做任务的就把他做了，把他的贡献加入一个小根堆中（贪心）；

如果遇到一个任务不能做了，但它比之前做过的任务的收益更高（即大于小根堆的堆顶），就放弃堆顶的那个任务，做这个任务

这样实现能保证答案最优。代码实现应该就很简洁明了了。

注：因为每完成一个工作需要的时间都是1，所以小根堆的size就是已经花费的时间。若任务i能完成，则Q.size()>a[i]的截止时间

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;

struct Node{
    int d, p; // 截止时间、获得收益
    friend bool operator < (Node p1, Node p2){
        return p1.d < p2.d; // 排序规则：按照截止日期从小到大排序
    }
}a[maxn];

void solve()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i].d >> a[i].p;
    sort(a + 1, a + n + 1);

    priority_queue <int, vector<int>, greater<int> > Q; // 小根堆，存储已完成任务的所有收益
    ll ans = 0; //! 开long long！！！
    for(int i = 1; i <= n; i ++){
        if(a[i].d > Q.size()){ // 不超时，正常加入
            Q.push(a[i].p);
            ans += a[i].p;
        }else{ // 超时的话，如果当前任务的报酬 大于 做完的任务报酬中最小的，就替换之前的任务
            if(a[i].p > Q.top()){
                ans -= Q.top(); Q.pop();
                ans += a[i].p;
                Q.push(a[i].p);
            }
        }
    }

    cout << ans << '\n';
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

拓展延申：反悔贪心是OI竞赛中的一个重要知识点，会和不会的区分非常明显。蒟蒻本人也在仔细研究。

献上我的研究成果：详细总结反悔贪心各种模型、刷题指南

让我们一起学习进步吧！

拜拜ヾ(•ω•`)o

原文地址：https://blog.csdn.net/YLCHUP/article/details/140403770

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！