做算法题最上头的一种感觉，就是明明写了一个“看起来没毛病”的贪心，兴致勃勃交上去，结果WA得一头雾水。P4053 [JSOI2007] 建筑抢修就是这类题里的经典代表，核心套路是“堆 + 后悔贪心”。先说清楚，这里的“堆”不是什么JVM堆内存，也不是Win11报错的那个栈溢出，而是数据结构里的优先队列。这道题完美展示了“把贪心做错了再反悔”的思考方式，属于只要吃透一次，以后遇到类似的调度题都能秒杀的模型。如果你正在刷贪心和堆的进阶题、被“为什么排序之后还要用堆”卡住，或者单纯想搞明白“后悔贪心”这四个字到底在说什么，这篇文章就是给你写的。

1. 先把问题吃透：建筑抢修到底在求什么

1.1 题目复述与样例推演

题目背景很简单：墙角有一堆建筑被损坏了，每个建筑需要固定的修复时间，并且每个建筑有一个截止时间，超过截止时间就算抢修失败。你同一时间只能修一栋楼，问你最多能抢修多少栋建筑。

输入是每栋建筑的“修理耗时”和“截止时间”，输出是能修复的最大数量。很多人第一反应是“这不就是排个序然后贪心吗”，网上搜到的题解也都写着“按截止时间排序 + 堆”，但真正自己动手写的时候，往往会在“什么时候用堆”“为什么要替换”这些地方卡住。

我构造一个最简单的例子演示一下：有四栋建筑，A需要耗时100，截止时间100；B、C、D分别需要耗时1，截止时间都是101。按截止时间排序后，A排在第一位。如果朴素地“能修就修”，你会选择先修A，修完花了100，剩下的B、C、D每个需要1，但此刻时间已经到100，B截止101，修完B正好101，勉强可以？不对，我们再算得严谨一点：修完A是100，修B需要1，100+1=101 ≤ 101，可以；修C需要1，101+1=102 > 101，不行。所以朴素贪心最多只能修A和B两栋。但最优解显然是放弃A，修B、C、D三栋，总共耗时3，远在截止时间之内。这个例子一摆出来，“能修就修”的漏洞就特别明显：前面一个耗时巨长的任务，会把后面一堆本来能轻松完成的小任务全部堵死。

1.2 朴素贪心为什么翻车

“按截止时间排序，能塞就塞”的朴素贪心，问题出在它把“当前能修”当成了“最终应该修”。实际上，某栋建筑此刻能修，不代表它值得修。当你把所有任务看成一条流水线，每个任务占用的时间是可以互相挤占的，先进入流水线的耗时大户未必比后进入的小任务更有价值。

用生活里的事类比：好比餐厅排队等位，前面那桌点了十个菜还要慢慢吃，后边进来的客人只要一份快餐。如果服务员只知道“谁先到谁先吃”，那快餐客人等半天也排不上，翻台率一塌糊涂。聪明的做法是看一眼桌面，发现前面那桌实在太慢，就让快餐客人先坐下吃，或者干脆请那桌只顾聊天不点菜的客人离开。建筑抢修的“后悔贪心”干的就是这事儿：先招待你，后边发现你太能占时间，就把你换下去。

朴素贪心的另一个问题是只关注局部最优。它每次判断“当前这栋楼能不能被塞进剩余时间里”，却没有全局回头看过往的选择。一个耗时很大的大楼即使自身能完成，也会导致后面成片的小楼超时。这种“一票否决”式的破坏力，只有通过主动放弃某个先前选择才能弥补。

1.3 关键观察：决策可以“反悔”

真正正确的解法，不是每一步都要想得完美，而是允许自己在后续步骤中推翻之前的决定。这个过程被称为“后悔贪心”，也叫“反悔贪心”，本质上是一种在贪心框架内引入撤销机制的策略。

具体操作是：先按照截止时间从小到大处理每栋建筑。每栋楼只要能放下，就先修，并把它的耗时记录到堆里。如果放不下，就看看当前这栋楼的耗时，是不是比已经选中的某些楼更短。如果是，就“反悔”掉之前耗时最长的那个选择，换成当前这栋楼。这样虽然选择数量没有增加，但是总耗时变小了，后面能塞进更多建筑。

这个思路的核心价值在于：它不追求每一步决策正确，只保证“已经选定的一批建筑”在任意时刻都是“在当前已扫描过的任务里，数量最多且总耗时最小”的组合。数量最多保证答案不会变小，总耗时最小保证后续有更大的容纳空间。

2. 后悔贪心 + 堆：天生一对的组合

2.1 后悔贪心是什么：先占坑再换人

“后悔贪心”这个名字容易把人吓住，好像是什么玄学高级技巧，其实内核特别朴素。普通的贪心是“做出选择，不再回头”，后悔贪心是“先按贪心选，但保留反悔能力”。

为什么需要反悔？因为单步贪心的依据是“当前看下来最划算”，但信息是逐步暴露的。在建筑抢修里，按截止时间排序处理到第i栋建筑时，你根本不知道后面还有多少耗时很短的楼在排队。如果你前面选了一个耗时100的大楼，后面冒出50个耗时1的小楼，从全局看前面那个选择就是彻头彻尾的败笔。这时候最好的补救方式不是“不能修超过截止时间的楼”，而是把耗时100的那栋从“已修列表”里踢出去，换成后面这些小楼。

这个“踢出去”的操作就是反悔。光有反悔还不够，还得做到“反悔成本最小”。什么选择最该被反悔？当然是“已选任务里耗时最长”的那个。因为踢掉它之后释放的时间最多，对整体约束的改善最大。于是问题就变成了：维护一个动态集合，反复查询“耗时最长的是谁”，并且还要支持删除和插入。这不就是堆的经典应用场景吗？

2.2 堆在“反悔”中扮演什么角色

堆在这里的任务非常具体：维护当前所有“已选中建筑”的修理耗时，随时能取出最大值。每处理一栋新楼，可能有三件事发生：

• 直接加入：总时间够用，楼被修好，耗时入堆。
• 替换：总时间不够，但新楼的耗时比堆里最大耗时小，则弹出最大值，把新楼插入。
• 跳过：总时间不够，新楼耗时又不比堆里的最大值小，则这栋楼只能放弃。

如果没有堆，每次找“耗时最长的已选建筑”就需要遍历整个已选集合，复杂度O(n)，叠加上n个任务就是O(n²)，数据量一大直接爆炸。用堆之后，插入、删除、取最大值都是O(logn)，整体复杂度降到O(nlogn)，这是这道题能过的关键。

注意这里的堆是大根堆，也就是堆顶是最大值。有人会直觉地以为“越小越好”应该用小根堆，但在后悔贪心模型里，被替换的对象是“最大耗时”的，所以必须用大根堆。我刚开始学的时候也在这一句上栽过跟头，把优先队列的默认大根堆当成了小根堆用，最后查了半天才发现是堆序反了。

2.3 为什么必须先按截止时间排序

排序是这道题另一个绕不开的点。很多人问：既然是要比较耗时大小，为什么不直接按耗时从短到长排？答案是：截止时间才是硬约束，耗时只是优化目标。

这里有一个经典的交换论证：任何一个可行的修复顺序，都可以在不破坏可行性的前提下，调整成按截止时间升序排列。假设有两栋建筑x和y，x截止时间更早，但当前顺序是先修y再修x。由于y在x之前完成，完成y的时刻一定小于完成x的时刻。如果把x挪到y前面，x本身更早截止都能满足，y的截止时间更晚，更不会出问题。所以按截止时间排序之后，我们实际上等于把所有建筑放进了一条固定时间轴，后面的决策只需要关注时间轴的推进，不再需要担心顺序交叉的复杂情况。

排序还有一个附带好处：它让“后悔”有了明确的边界条件。当按截止时间处理到某一栋楼时，之前所有楼都满足“自己的截止时间早于当前楼”，所以只要整体总耗时不超过当前楼的截止时间，前面那些楼就必然不会超时。于是，全局约束被简化成了“当前累计耗时不能超过当前楼的截止时间”。

2.4 替换操作为什么不会破坏正确性

这是整个算法最需要证明的部分。直觉上，把一栋耗时长的楼换成一栋耗时短的楼，总耗时变小了，怎么想都不会更差。但严谨地说，替换会不会导致之前某些楼满足不了的截止时间突然又不满足了？不会，因为总耗时变小，完成每个任务的时间只会更早。

展开说：在替换之前，设当前已选集合S，总耗时为T，集合里所有任务都按截止时间排序且全部满足约束。现在从S里移除耗时最大的任务u，插入新任务v，且v的耗时小于u，则新的总耗时T'小于T。原来在T的方案下，每个任务的完成时间都不晚于其截止时间；现在总耗时更小，相当于每个任务的完成时间整体前移，所以原来能满足的截止时间现在照样满足。唯一需要额外检查的是v自身的截止时间，但v是当前正在处理的建筑，它的截止时间比之前所有建筑都晚，而替换后v的完成时间甚至比原来u的完成时间更早，而原来u的完成时间不超过u的截止时间，u的截止时间又不晚于v的截止时间，所以v绝对满足。这一串比较下来，替换的安全性就有了保证。

从结果上看，替换不改变已选建筑的数量，但减少了总耗时，给后续建筑腾出了更多空间。这正是“数量不变、质量提升”的操作，反复执行之后，算法最终得到的集合一定是在全部n栋建筑中“数量最多且总耗时最小”的可行解。

3. 完整代码实现与逐行拆解

3.1 可直接提交的C++代码

直接给出一版能AC的核心代码，注释写得很详细，方便直接抄作业。

#include <bits/stdc++.h> using namespace std; using ll = long long; struct Node { ll need; // 修复耗时 ll limit; // 截止时间 }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<Node> a(n); for (int i = 0; i < n; i++) { cin >> a[i].need >> a[i].limit; } // 1. 按截止时间升序排序 // 截止时间相同的情况下，耗时短的排前面，不影响结果，单纯为了有序 sort(a.begin(), a.end(), [](const Node& x, const Node& y) { if (x.limit != y.limit) return x.limit < y.limit; return x.need < y.need; }); // 2. 大根堆维护已选建筑的耗时，堆顶是耗时最长的 priority_queue<ll> pq; ll now = 0; // 当前已选建筑的总耗时 int ans = 0; // 已选建筑数量 for (const auto& node : a) { // 情况1：当前楼可以直接塞进剩余时间 if (now + node.need <= node.limit) { pq.push(node.need); now += node.need; ans++; } // 情况2：塞不下，但当前楼比已选里耗时最长的楼更短 // 那就反悔：丢掉耗时最长的，换成当前楼 else if (!pq.empty() && node.need < pq.top()) { now -= pq.top(); pq.pop(); pq.push(node.need); now += node.need; } // 情况3：塞不下，当前楼又不短，直接跳过 } cout << ans << "\n"; return 0; }

3.2 排序规则与堆操作细节

排序部分，优先队列的默认行为必须在脑子里过一遍。C++的priority_queue<ll>默认是大根堆，堆顶是最大值。如果你自己写小根堆，比如priority_queue<ll, vector<ll>, greater<ll>>，那整个替换逻辑的方向就反了，会把“最小耗时”弹出去，结果完全错误。

再看替换逻辑。很多人在else if里会纠结要不要加!pq.empty()这个条件。我的建议是保留，原因很直接：如果第一栋楼本身就修不了（截止时间小于耗时），此时堆是空的，pq.top()会触发未定义行为，程序直接崩掉。虽然实际数据里第一栋楼往往能修，但竞赛里养成“访问堆顶前先判空”的习惯绝对值得。

now -= pq.top(); pq.pop(); pq.push(node.need); now += node.need;这段操作等价于“用新楼替换掉旧楼”，但要注意，是在now上先减后加，顺序不能乱。如果先push再pop，虽然堆的内容一样，但now的同步更新会容易写错。保持“先弹出旧值更新now，再插入新值更新now”的顺序，逻辑最清晰。

3.3 复杂度与数据范围分析

时间上，排序O(nlogn)，每个任务最多一次插入和一次弹出，每次堆操作O(logn)，总体O(nlogn)。空间上，堆里最多存当前已选建筑，O(n)。

数据范围方面，修复耗时和截止时间都可能比较大，累加总耗时更是可能超过int的范围。很多初学者在这个题上WA，不是算法不对，而是int now爆了。我建议所有涉及时间累加的变量一律用long long，结构体里的字段也用long long。虽然题目数据可能比较温和，但写代码时把类型往大了开，是竞赛里成本最低的保险。

4. 实战中的坑与调试心得

4.1 最容易踩的四个坑

第一个坑是“比较符号方向搞反”。替换条件是node.need < pq.top()，也就是新楼比旧楼更短才换。如果是<=，等于的情况下替换不影响总耗时，但也没意义，白白多一次操作；如果写成>，那就是把短的换掉留长的，算法直接退化成错误贪心，答案越跑越差。

第二个坑是“截止时间排序搞反”。有人会把limit和need搞混，按耗时排完序，然后整个算法全部错乱。一个简单的自测样例就是第1章那个“耗时100截止100 + 三个耗时1截止101”的例子，如果你的排序关键字不对，跑出来的答案一定不对。

第三个坑是“忘了同时维护now”。pq是堆顶对应旧楼，但now是总耗时，两者必须同步更新。我见过有人只更新堆不更新now，结果后续判断全错，还以为是堆的问题，排查了半天。

第四个坑是“没有判堆空”。前面提过，第一栋楼可能就满足不了条件，此时else if里如果直接访问pq.top()，对于某些编译器来说会返回垃圾值，运气好没崩，运气差直接RE。判空一下又不多费事，别省。

4.2 相等与边界情况怎么处理

处理到截止时间相同的一批建筑时，排序的稳定性不重要，但要注意内部的判定条件。now + node.need <= node.limit里是小于等于，等于的情况表示恰好卡在截止时刻完成，属于可以修的状态，别写成严格小于。

替换条件node.need < pq.top()是严格小于。如果等于，替换没有意义，还多一次pop和push，虽然不影响结果，但会让调试时多一步困惑。边界场景是node.need == pq.top()且塞不下，此时不替换是对的，因为换了总耗时没变，后面照样塞不下。

另一种边界情况是总耗时已经很大，堆里最小元素都比当前楼大，也就是当前楼不具备任何竞争力，直接跳过即可。这个场景由else if自然覆盖，不用额外写逻辑。

4.3 刷题阶段怎么验证思路对不对

很多人刷题时直接看题解，看完觉得懂了，一写又错。我的习惯是先不看题解，自己写一个朴素贪心和一个暴力搜索，在小数据上对拍，找出朴素贪心的反例，然后带着反例去看正确解法。P4053这个题，暴力搜索可以用DFS枚举所有子集，n在15以内就能跑。对拍脚本不需要多高级，用Python或C++生成随机小数据，分别跑朴素版和正解版，对比输出即可。

我自己当年就是这么干的：先写一个按截止排序、能塞就塞的朴素版，再用全排列或状态压缩暴力找最优解，跑几组随机数据后果然发现了反例。这时候再去看“替换耗时最长的”这个操作，就特别有感觉，因为它不是凭空冒出来的技巧，而是针对反例设计的修复手段。建议你也试试这个过程，对“后悔贪心”的理解会深入很多。

5. 从P4053延伸：后悔贪心的“通杀”模型

5.1 一眼识别后悔贪心的三个特征

刷题多了你会发现，后悔贪心其实是一类题型的通用解法，建筑抢修只是它的一个漂亮外壳。识别这类题，我总结出三个特征：

第一，问题里有一个“截止时间”或“容量上限”之类的硬性约束，不满足就不能选。第二，目标是在约束下最大化选择数量或者收益。第三，每个元素有一个“代价”属性，比如耗时、占用空间、成本，而且代价是可比较、可替换的。只要同时命中这三点，就可以优先考虑“排序 + 堆 + 后悔”的套路。

这三个特征背后共同的逻辑是：贪心先按某个关键属性排序，用堆维护一个“可反悔”的候选集合，当新元素因为约束放不进去时，尝试用更优的代价替换集合中的最差元素，从而在不改变数量的前提下降低总代价，为后续元素腾出空间。

5.2 相似题与变形思路

最经典的相似题是P2949 [USACO09OPEN] Work Scheduling，工作调度。那道题是每项工作有截止时间和利润，单位时间只能做一项工作，问最大利润。解法也很类似：按截止时间排序，用小根堆维护已选工作的利润，每当新工作截止时间不满足时，如果新工作利润比堆里最小利润高，就替换掉利润最低的工作。注意那里用的是小根堆，因为要淘汰“利润最低”的，和这道题淘汰“耗时最长”的大根堆正好构成镜像。

还有一类“可以反悔的股票买卖”问题，用堆维护之前的最低买入价，当出现更高卖出价时，把差价收益加入答案，并重新把价格入堆，为后续可能的多次反悔做准备。这类题的精髓都是同一个：让数据结构帮你在常数时间内找到“最该被反悔的选项”。

如果你想把这类题练透，建议按这个顺序刷：P4053建筑抢修、P2949工作调度、然后去找几道带截止时间的区间调度题。刷完你会发现，很多题的题解写着“堆 + 贪心”，其实都是同一套后悔模型的变体，换汤不换药。

5.3 后续还可以往哪个方向扩展

后悔贪心还可以和二分答案结合。有些题目不要求输出具体方案，直接问“最多能完成多少个”，可以先二分数量k，然后用类似的堆策略验证能否完成k个，复杂度变成O(nlog²n)。甚至某些变体里，“代价”不是单一的数字，而是一个多维属性，这时候堆的结构也要跟着调整，比如用pair存“耗时+编号”，方便定位被替换的元素是谁。

不过对于P4053本身，最值得掌握的还是那个干净利落的思路：排序给后续决策建立时间轴，堆维护反悔的最小成本，替换保证数量不减、质量更优。这个模型几乎可以无缝迁移到所有“资源受限、最大化数量”的调度题里，是我刷题到现在觉得性价比最高的一类贪心。

最后再分享一个做题习惯：遇到这种“看答案秒懂、自己想不出来”的题，别急着背题解。先把朴素贪心写出来，再构造反例，然后观察“到底哪一步决策需要被推翻”。一旦亲手抓到那个反例，你就明白堆在替你做哪件事了，以后遇到类似的题，哪怕忘了具体代码，也能顺着这条思路重新推出来。