反悔贪心学习笔记[浅谈]
贪心是信息学竞赛常考内容，一般来说为选择当前情况下最优情况的算法，非常好写，但部分贪心题目无法使用普通贪心解决，在这些题目中就有一类为反悔贪心。
反悔贪心经常会用到堆来为主答案，例题：
Work Scheduling G
本题很容易发现可以使用贪心来解决，具体地，我们将读入的数据按照
T
2
T2
T2 从小到大排序，然后遍历一遍，然后先把所需要的时间加到
s
u
m
sum
sum 中然后将这次所用的时间放入一个大根堆中，然后判断
s
u
m
sum
sum 是否大于当前的
T
2
T2
T2 如果小于那么直接修理建筑
a
n
s
+
+
ans++
ans++，否则就体现出反悔贪心的精髓了，我们把大根堆堆顶的数删去，然后从
s
u
m
sum
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;
}