反悔贪心学习笔记

算法：

反悔贪心，顾名思义就是贪心的时候 反悔。

意思是：如果这一步的贪心 不是全局最优解，就退回去一步，换一种贪心策略。

一般分为 反悔自动机 和 反悔堆。

反悔自动机基本的思路是：每次选择直观上 最接近全局最优解 的贪心策略，若发现最优解不对，就想办法 自动 支持反悔策略。

反悔堆则是：通过 堆 来维护当前贪心策略的最优解，若发现最优解不对，就 退回上一步，更新最优解。

题目：

题单：link

模板题：P4053 建筑抢修

link

首先我们将 \(t2\) 从小到大排序。

然后用大根堆维护每一个元素。

在贪心的过程中，若发现目前不是最优解，那么就取堆顶元素，来保证正确性。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+10;
ll n,ans,s;
priority_queue<ll> q;
struct P{
	ll t1,t2;
}a[N];
bool cmp(P l,P r){
	return l.t2<r.t2;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].t1>>a[i].t2;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		s+=a[i].t1,q.push(a[i].t1);
		if(s<=a[i].t2) ans++;
		else s-=q.top(),q.pop();
	}
	cout<<ans;
	return 0;
}

热门相关：隐婚99天：首席，请矜持   婚婚欲睡：腹黑老公请节制   呆萌配腹黑：欢喜小冤家   呆萌小萝莉：高冷男神太腹黑   穹顶之上