反悔贪心学习笔记[浅谈]

贪心是信息学竞赛常考内容，一般来说为选择当前情况下最优情况的算法，非常好写，但部分贪心题目无法使用普通贪心解决，在这些题目中就有一类为反悔贪心。

反悔贪心经常会用到堆来为主答案，例题：
Work Scheduling G
本题很容易发现可以使用贪心来解决，具体地，我们将读入的数据按照 $T2$ 从小到大排序，然后遍历一遍，然后先把所需要的时间加到 $sum$ 中然后将这次所用的时间放入一个大根堆中，然后判断 $sum$ 是否大于当前的 $T2$ 如果小于那么直接修理建筑 $ans++$，否则就体现出反悔贪心的精髓了，我们把大根堆堆顶的数删去，然后从 $sum$ 中减去大顶堆中的数(所需时间)，因为大顶堆顶的数是最大的，所以减去后可以省下最多的时间，及之后可以修更多的建筑。

由此获得 Code

#include<bits/stdc++.h>
using namespace std;
struct node{int t1,t2;
}a[150005];
bool cmp(node x,node y)
{return x.t2<y.t2;
}
long long n,ans,sum;
priority_queue<int> q;
signed main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i].t1>>a[i].t2;sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){sum+=a[i].t1;q.push(a[i].t1);if(sum<=a[i].t2)ans++;else{sum-=q.top();q.pop();}}cout<<ans<<"\n";return 0;
}