本文主要是介绍算法竞赛---反悔贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
反悔贪心
Work Scheduling G
什么是返回贪心呢，就是先选择，遇到更好的之后在反悔选择更好的，这是符合贪心的逻辑的。
#include <bits/stdc++.h>
// https://www.luogu.com.cn/problem/P2949
using namespace std;
struct node
{int d, p;bool operator<(node &b){return d < b.d;}
} w[100005];
long long ans;
priority_queue<int, vector<int>, greater<int>> q;
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> w[i].d >> w[i].p;}sort(w + 1, w + n + 1); // 按照时间进行排序for (int i = 1; i <= n; i++){// 队列里面有几个q.size（） 就是最长的时间了// 如果和时间相等的话,把队列最前面的取出来进行比较if (w[i].d == q.size()) // 这个如何理解呢？如果w的d就是时间等于q的size（）{if (w[i].p > q.top()){ans -= q.top();q.pop();q.push(w[i].p);ans += w[i].p;}}else{q.push(w[i].p);ans += w[i].p;}}cout << ans;
}
代码的分析
首先分析题目，在截止时间之前需要完成，我们可以用struct结构体来存储对应的截止时间和价值，根据截止时间进行排序。for循环遍历，添加到队列中去，如果要添加的截止时间等于优先队列的长度，表示在这个时间内也可以做这件事情，就需要判断即将添加进来的这件事情的价值和优先队列中的最小价值比较，如果队列里面的最小价值小，那么就将其出队，再把新的添加进去。
这篇关于算法竞赛---反悔贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
