做算法题最上头的一种感觉就是明明写了一个“看起来没毛病”的贪心兴致勃勃交上去结果WA得一头雾水。P4053 [JSOI2007] 建筑抢修就是这类题里的经典代表核心套路是“堆 后悔贪心”。先说清楚这里的“堆”不是什么JVM堆内存也不是Win11报错的那个栈溢出而是数据结构里的优先队列。这道题完美展示了“把贪心做错了再反悔”的思考方式属于只要吃透一次以后遇到类似的调度题都能秒杀的模型。如果你正在刷贪心和堆的进阶题、被“为什么排序之后还要用堆”卡住或者单纯想搞明白“后悔贪心”这四个字到底在说什么这篇文章就是给你写的。1. 先把问题吃透建筑抢修到底在求什么1.1 题目复述与样例推演题目背景很简单墙角有一堆建筑被损坏了每个建筑需要固定的修复时间并且每个建筑有一个截止时间超过截止时间就算抢修失败。你同一时间只能修一栋楼问你最多能抢修多少栋建筑。输入是每栋建筑的“修理耗时”和“截止时间”输出是能修复的最大数量。很多人第一反应是“这不就是排个序然后贪心吗”网上搜到的题解也都写着“按截止时间排序 堆”但真正自己动手写的时候往往会在“什么时候用堆”“为什么要替换”这些地方卡住。我构造一个最简单的例子演示一下有四栋建筑A需要耗时100截止时间100B、C、D分别需要耗时1截止时间都是101。按截止时间排序后A排在第一位。如果朴素地“能修就修”你会选择先修A修完花了100剩下的B、C、D每个需要1但此刻时间已经到100B截止101修完B正好101勉强可以不对我们再算得严谨一点修完A是100修B需要11001101 ≤ 101可以修C需要11011102 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和yx截止时间更早但当前顺序是先修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; vectorNode 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_queuell 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_queuell默认是大根堆堆顶是最大值。如果你自己写小根堆比如priority_queuell, vectorll, greaterll那整个替换逻辑的方向就反了会把“最小耗时”弹出去结果完全错误。再看替换逻辑。很多人在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本身最值得掌握的还是那个干净利落的思路排序给后续决策建立时间轴堆维护反悔的最小成本替换保证数量不减、质量更优。这个模型几乎可以无缝迁移到所有“资源受限、最大化数量”的调度题里是我刷题到现在觉得性价比最高的一类贪心。最后再分享一个做题习惯遇到这种“看答案秒懂、自己想不出来”的题别急着背题解。先把朴素贪心写出来再构造反例然后观察“到底哪一步决策需要被推翻”。一旦亲手抓到那个反例你就明白堆在替你做哪件事了以后遇到类似的题哪怕忘了具体代码也能顺着这条思路重新推出来。