反悔贪心 (Regretful Greedy)：动态试错与优先队列维护

一、优先队列：随时取出当前最值

1. 什么是优先队列？

普通的队列（Queue）就像在食堂打饭，讲究“先来后到”（FIFO：先进先出）。而优先队列（Priority Queue）就像医院的急诊室，讲究“轻重缓急”。不管你什么时候排进来，系统都会让极值（最大或最小的元素）排在第一个。

时间复杂度：插入一个元素是 $O(\log N)$ ，查询最值是 $O(1)$ ，弹出一个最值是 $O(\log N)$ 。
非常适合那种“不断有新元素加入，且随时需要知道当前最大值/最小值”的场景。

2. C++ STL 中的优先队列

在 C++ 中，优先队列包含在 #include<queue> 头文件中。它分为两种极值形态：

形态一：大根堆（默认）

永远把最大的元素顶在最前面。

priority_queue<int> max_heap;

形态二：小根堆

永远把最小的元素顶在最前面。它的写法比较长，必须死记硬背：

priority_queue<int, vector<int>, greater<int>> min_heap;

3. 核心操作指令

无论是大根堆还是小根堆，它们的操作指令完全一样：

q.push(x);  // 将元素 x 放入队列，系统会自动调整它到合适的位置
q.top();    // 获取当前队列中的“极值”（大根堆就是最大值，小根堆就是最小值）
q.pop();    // 将队列的“极值”踢出队列（注意：无返回值）
q.size();   // 返回队列里当前有几个元素
q.empty();  // 检查队列是否为空，空返回 1，非空返回 0

有了这个能随时帮我们找到“极值”的兵器，我们就可以正式开启反悔贪心之旅了。

二、从普通贪心到“后悔药”

普通的贪心算法常常面临一个致命缺陷：“鼠目寸光，落子无悔”。为了眼前的局部最优，可能不小心堵死了后续全局更优的道路。

反悔贪心的精髓在于：我们依然先无脑做出当前看起来最赚的选择，但在做选择的同时，把“后悔药”存起来。当未来遇到更好的选项、但资源（时间/空间）不够时，我们就吃下后悔药，撤销之前性价比最差的决定，替换成当前更好的决定。

反悔贪心：用更高利润任务替换最低利润

1. 核心例题剖析：P2949 工作调度

1. 寻找基础贪心基准线：普通贪心为什么会失效？

面对“截止日期”和“利润”，直觉会产生两种基础贪心策略：

错误策略 A（利润优先，且从最早的空位开始安排）：一看到利润最大的工作，就马上占掉前面的时间。
- 翻车原因：如果利润最大的工作截止时间非常晚，一开始就去做它，会挤占宝贵的时间，导致许多即将到期、利润也不错的工作白白过期。
错误策略 B（只看截止日期）：按截止时间 $D_i$ 从小到大排序，快到期的先做。
- 翻车原因：如果快到期的工作利润极低（如 1 块钱），而后面有一个利润 1000 块的工作，却因为时间排满做不了，这就捡了芝麻丢了西瓜。

2. 引入小根堆，实现“动态反悔”

别误伤另一种正确贪心：按利润从大到小、每次安排在截止日期前最晚的空位，也能做这题。我们这里专门讲“截止日期排序 + 小根堆”的路线。

为了解决“按截止时间贪心可能选到极低利润”的问题，我们引入小根堆来实现动态反悔。

核心模型推导：

统一基准：首先，必须按照截止时间 $D_i$ 从小到大排序。保证时间轴向前推进，绝不出现“时光倒流”。
容量限制机制：每个任务耗时 1 个单位。已经安排的任务全部塞在优先队列 pq 里，因此 pq.size() 就代表了当前花掉的天数。
试错与反悔：
- 遍历到一个新任务时，如果当前花费的天数还未达到该任务的截止时间（即 pq.size() < D_i），说明还有空闲日子。无脑接下这个任务，将利润压入小根堆，总收益累加。
- 如果 pq.size() >= D_i，日子排满了。这时看堆顶（即已经接下的所有任务中，利润最低的那个任务）。
- 如果当前新任务的利润 $P_i$ 大于堆顶任务的利润 pq.top()，果断反悔！踢掉堆顶任务（总收益减去它，pq.pop()），换成当前的高利润任务（总收益加上新利润，pq.push(P_i)）。

原理解析：为什么踢掉旧任务，新任务一定能塞进去？

因为我们是按截止时间排序的！新任务的截止时间 $D_i$ 必定大于等于被踢掉任务的截止时间。既然被踢任务在以前都能合法安排下，把它的时间槽腾出来，给截止时间更宽裕的新任务，绝对是 100% 合法的。

2. 标准求解算法与模板

代码严格遵循结构化封装，使用 greater<int> 声明小根堆来维护最低利润。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

struct Node{
	int d,p;
	bool operator<(const Node& x)const{
		// 按截止日期从小到大排序
		return d<x.d;
	}
}a[N];

int n;
// 声明一个小根堆，随时准备把利润最小的决策踢出去
priority_queue<int,vector<int>,greater<int>> pq;

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].d>>a[i].p;
	}
	
	// 1. 按截止时间排序，保证时间轴向前推进
	sort(a+1,a+1+n);
	
	int ans=0;
	for(int i=1;i<=n;i++){
		// 2. pq.size() 就是当前已经消耗的天数
		if(a[i].d>pq.size()){
			// 有空位，直接无脑接下
			pq.push(a[i].p);
			ans+=a[i].p;
		}else if(!pq.empty()&&a[i].p>pq.top()){
			// 没空位了，但当前任务比已选的最差任务更赚钱，启动反悔
			ans-=pq.top(); // 扣除后悔的低利润
			pq.pop();      // 踢出堆
			pq.push(a[i].p);
			ans+=a[i].p;   // 加上当前高利润
		}
	}
	cout<<ans<<'\n';
}

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

3. 知识拓展：静态反悔与动态反悔的区别

反悔贪心根据限制条件爆发的时机，分为动态与静态两类。

💡 1. 动态反悔：随时间推进 (如 P2949 工作调度)

特征：限制条件分布在每一个时间节点上（每个 $D_i$ 都是一个局部限制）。
处理方式：必须依赖优先队列（大根堆/小根堆），在遍历的过程中边走边判断，随时剔除最差决策。

💡 2. 静态反悔：一次性结算（如洛谷 P14361 [CSP-S 2025] 社团招新）

特征：限制条件是全局唯一的（如：没有任何部门可以超过 $\frac{n}{2}$ 人）。在所有人无脑做完局部最优选择后，限制才在最后统一爆发。
处理方式：不需要优先队列。只需计算撤销每个决定的“反悔差值”，将超标的部分单独拎出来，进行一次普通的从小到大排序，挑出代价最小的前 $k$ 个人强制反悔并扣除代价即可。

三、变种模型：多耗时任务的“时间压榨”

1. 物理推导：从“踢最不赚钱”到“踢最费时间”

如果任务不再是每天只能做一个，而是每个任务耗时 $T_i$ 不同，且都有严格的截止时间 $D_i$ ，问最多能完成几个任务？

错误直觉：按耗时最短优先？可能会错过那些虽然短但马上就要截止的任务。按截止时间优先？遇到一个耗时极长的任务，一旦接下，可能会把后面的时间轴全部堵死。
反悔贪心策略：依然按截止时间 $D_i$ 从小到大排序，保证时间轴稳定推进。
我们维护一个大根堆，里面存的是已经接下的任务的耗时 $T_i$ 。
遇到新任务，如果 当前已用总时间 + T_i <= D_i，说明时间足够，无脑接下，把 $T_i$ 扔进堆里。
如果时间超了，看一眼堆顶（也就是当前已选任务中，耗时最长的那个“磨洋工”任务）。如果新任务的耗时 $T_i$ 比堆顶小，果断反悔！踢掉堆顶任务，换成当前耗时短的新任务。

物理意义：既然每个任务的贡献都是 1（只算完成数量），用耗时短的替换耗时长的，能够在保证完成总数不掉的前提下，硬生生腾出更多的时间，留给未来的任务去挥霍。

2. 手算推演小例子

假设有 3 个任务 (耗时 $T$ , 截止时间 $D$ )：A(5, 5)，B(2, 6)，C(3, 7)。按照截止时间排序已经是 A, B, C。

遇见 A(5, 5)：当前时间 0。0 + 5 $\le$ 5，接下 A！
- 当前时间变成 5，堆里有 [5]。完成数量 1。
遇见 B(2, 6)：当前时间 5。5 + 2 = 7 $>$ 6，超时了做不了。
- 对比堆顶：B 耗时 2，堆顶 A 耗时 5。2 $<$ 5，启动反悔！
- 踢掉 A，接下 B。当前时间变成 5 - 5 + 2 = 2。堆里变成 [2]。
- 完成数量依然是 1，但我们把时间轴从 5 倒退回了 2，赚到了 3 天时间！
遇见 C(3, 7)：当前时间 2。2 + 3 = 5 $\le$ 7，时间充足，接下 C！
- 当前时间变成 5，堆里有 [3, 2]。完成数量变为 2。

结果：最多完成 2 个任务。如果当初不吃“后悔药”死抱着 A 不放，后面根本没时间做 B 和 C。

3. 代码实现与被选集合恢复

很多题目不仅问“最多做几个”，还会问“具体做了哪几个”。由于优先队列里默认只存耗时，弹出来时根本不知道是谁。技巧：在堆里存结构体，或者利用 pair，把原始下标和耗时绑定在一起。当整个循环结束时，堆里幸存下来的那些元素的下标，就是最终选中的任务。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200005;

struct Task {
	int t, d, id;
	bool operator<(const Task& other) const {
		return d < other.d; // 外层：按截止时间从小到大推进
	}
} a[N];

struct HeapNode {
	int t, id;
	bool operator<(const HeapNode& other) const {
		return t < other.t; // 堆内：按耗时构造大根堆，把最耗时的顶到最前面
	}
};

int n;
priority_queue<HeapNode> pq;

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].t >> a[i].d;
		a[i].id = i; // 提前记录原始下标，防止排序后迷路
	}
	
	sort(a + 1, a + 1 + n);
	
	int current_time = 0;
	for (int i = 1; i <= n; i++) {
		if (current_time + a[i].t <= a[i].d) {
			// 时间够，直接接下
			current_time += a[i].t;
			pq.push({a[i].t, a[i].id});
		} else if (!pq.empty() && pq.top().t > a[i].t) {
			// 时间不够，但当前任务更省时，踢掉堆顶的耗时大户
			current_time -= pq.top().t;
			pq.pop();
			
			current_time += a[i].t;
			pq.push({a[i].t, a[i].id});
		}
	}
	
	// 输出最多能完成几个任务
	cout << pq.size() << '\n';
	
	// 恢复被选集合：此时堆里剩下的就是答案
	vector<int> chosen;
	while (!pq.empty()) {
		chosen.push_back(pq.top().id);
		pq.pop();
	}
	sort(chosen.begin(), chosen.end()); // 按原序号排个序方便输出
	for (int i = 0; i < chosen.size(); i++) {
		cout << chosen[i] << (i == chosen.size() - 1 ? "" : " ");
	}
	cout << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}
/*
【自拟样例】
输入：
3
5 5
2 6
3 7
输出：
2
2 3
*/

四、避坑指南：堆不能保证所有的贪心正确

在前面的模型中，反悔之所以敢无脑进行，是因为存在极其严密的等价交换依据。

在“工作调度”中，每份工作都只占用 1 天时间。用高利润换低利润，总耗时不变，对未来毫无影响。
在“时间压榨”中，每份工作都只贡献 1 个完成数。用短任务换长任务，完成数不变，对未来甚至还倒赚了时间。这叫“1换1”的底线。

1. 警惕双变量失控的陷阱

如果题目变成：有 $N$ 个任务，每个任务有不同的耗时 $T_i$ 、不同的截止日期 $D_i$ ，并且还有不同的利润 $P_i$ 。你还能用优先队列“踢最小利润”或者“踢最大耗时”吗？

绝对不行！ 如果按利润反悔，你踢出一个利润低但耗时仅仅 1 分钟的任务，换进一个利润高一点、却耗时 10 天的任务。此时堆完全无法评估这个长达 10 天的“黑洞”会导致后面多少个任务直接过期作废。一旦失去等价交换的单变量控制，模型本质上已经退化为带有时间维度的 0-1 背包问题，只能请出动态规划 (DP) 来进行全局状态转移了。

反悔贪心