堆+后悔贪心：建筑抢修问题全解与任务调度应用

P4053 [JSOI2007] 建筑抢修 是一道非常经典的“堆 后悔贪心”入门题。题面一句话就能说完有 n 栋建筑每栋需要消耗一定的修理时间并且有一个截止时间同一时刻只能修一栋问最多能抢修多少栋。乍一看像动态规划但真正动手做的时候你会发现排序 大根堆 超时弹出最大耗时十来行代码就能通过而且思路一旦打通同类题基本都能横扫。这篇文章适合正在学贪心和堆的 OI 选手、准备笔试面试的开发者也适合日常需要做任务排期的朋友。我会把这道题从“为什么这么贪心”到“代码怎么写”完整拆开再附上我实际调试时踩过的坑和验证方法。看完你不仅能 A 掉这道题还能把“后悔贪心”这个套路搬到工作调度、活动选择、任务取舍这些场景里去。1. 先别急着写代码把问题彻底读懂1.1 题面里藏着哪些关键信息原题的大意是有 n 栋建筑每栋建筑有两个参数一个是修理这栋建筑需要花的时间 T1另一个是这栋建筑的截止时间 T2。修理工作只能一个一个来不能并行。如果某栋建筑在 T2 时刻或更早完成修理就算“抢修成功”否则这栋就算报废。目标是让成功抢修的建筑数量尽可能多。这里最容易忽略的是“同一时间只能修一栋”。很多新手会往背包 DP 或者二分图匹配上想但实际上资源约束非常单一总时间是一条直线每个任务占用一段连续区间任务之间不能重叠只能顺延。从这个角度看它本质上是一个“单位时间资源分配”问题而这类问题往往用贪心比 DP 更直接。1.2 这道题到底在问什么你可以把修理过程想象成一条流水线。每个建筑就是一个待加工的任务任务有加工时长也有交货截止时间。问题变成如何选择一批任务安排它们按某种顺序加工让每个任务都能在截止时间之前完工并且选择的任务数量最多。注意这里的顺序是可以自由调整的。对于任何一个选定的任务集合如果存在一种排列使所有任务都能按时完成那么把它们按截止时间从小到大排序后同样能按时完成。这个性质叫“EDD 序最优”也就是最早截止时间优先。它是后面所有贪心策略的地基。所以这道题真正要回答的是在“按截止时间排序”这条时间线上我们应该放弃哪些任务才能让最终留下的任务数量最多。直接想这个问题很困难因为放弃一个任务不仅影响当前数量还影响后续所有任务的可用时间。1.3 为什么“堆 后悔贪心”会成为经典组合因为这个问题天然适合“在线决策 事后反悔”。我们从前往后扫描按截止时间排好序的任务每看到一个任务先假设它要修把它放进当前方案里。如果放进之后发现无法满足当前这个任务的截止时间说明当前方案里必须扔掉一个任务。扔掉哪个直觉告诉我们应该扔掉耗时最长的那个因为这样腾出来的总时间最多对后续任务最有利。要快速找到耗时最长的任务堆就是最顺手的工具。一个大根堆维护当前方案里所有任务的修理耗时超时的时候弹出堆顶O(log n) 解决。整个过程走一遍只需要 O(n log n)n 最大可以到 15 万级别完全没问题。这个组合因此成了“后悔贪心”的标准模板。2. 从错误直觉到正确方向贪心策略的推倒重建2.1 第一个想法按耗时排序能不能行很多人第一反应是既然希望修的数量多那当然优先修耗时短的建筑。比如两栋建筑一个耗时 1 天截止 100 天一个耗时 2 天截止 3 天如果只按耗时排先修耗时 1 天的第二栋就赶不上截止时间只能修 1 栋但如果先修耗时 2 天的第一栋完全来得及能修 2 栋。这说明单纯按耗时排序是错的因为截止时间同样约束着任务顺序。也有同学会想用“性价比”即耗时除以截止时间之类的东西排序。这个思路在类似“分数背包”的问题里有效但在这里任务的收益不是价值而是数量每栋建筑对答案的贡献都是 1不满足分数背包的连续性。你没法修半栋所以这类排序同样站不住脚。2.2 第二个想法按截止时间排序再顺势贪心既然 EDD 序最优那自然想到把建筑按截止时间从小到大排序然后从头开始修能修就修。维护一个当前总耗时 sum遇到下一栋建筑时如果 sum T1 T2就修它sum T1如果放不进去就直接跳过。这个做法比按耗时排序合理得多但仍然有问题。问题出在“能修就修”太死板。当前建筑放不进去不代表应该放弃它。有可能之前选的某栋建筑特别耗时把时间全占了如果当时不选那栋现在这栋就能塞进去。换句话说早期决策可能会堵死后期的路而直接跳过当前任务并没有解决“之前选了个巨无霸”这个隐患。2.3 用一个反例说明直觉哪里出了问题我们造一组数据感受一下。四栋建筑如下A耗时 5截止 10B耗时 3截止 11C耗时 4截止 12D耗时 10截止 100按截止时间排序后是 A、B、C、D。如果采用“能修就修”修 Asum 5修 Bsum 8 11遇到 Csum 4 12 12刚好能修sum 12遇到 Dsum 10 22 100没问题可以修最终修 4 栋。这个例子不够典型换一组A耗时 7截止 8B耗时 2截止 10C耗时 2截止 12按截止排序后 A、B、C。如果“能修就修”修 Asum 7 8修 Bsum 9 10遇到 Csum 2 11 12可以修最终修 3 栋。这组也没问题。真正会出问题的是这种情况A耗时 6截止 6B耗时 5截止 11C耗时 5截止 16“能修就修”A 修完 sum 6B 修完 sum 11 11C 无法修sum 5 16 16刚好 16其实可以修最终 3 栋。还是不炸。再找一个必然炸的反例。核心矛盾是一个耗时很长的任务占据了时间导致后续多个短任务无法加入。A耗时 100截止 100B耗时 1截止 101C耗时 1截止 102D耗时 1截止 103按截止排序 A、B、C、D。“能修就修”修 A 后 sum 100B、C、D 都无法加入最终只修 1 栋。但明显最优方案是放弃 A修 B、C、D可以修 3 栋。这就是“能修就修”的最大缺陷一个早期的大耗时任务会把后面所有机会全部堵死。3. 后悔贪心的完整推导一个堆解决的“丢车保帅”3.1 后悔操作的直观理解“能修就修”失败的根本原因在于它不允许反悔。而现实中我们做任务安排经常需要“调整优先级”——发现某个任务塞不下时与其放弃新任务不如看看已经安排的任务里有没有哪个耗时特别长、可以踢出去的。踢掉一个旧任务、换上新任务这个操作就是“后悔”。它不是真的时光倒流而是把“当前方案”这一个集合动态维护成最优。具体到这道题按截止时间逐一看每栋建筑先假设当前建筑要修把它的耗时加入总时间如果加入后发现总时间超过了当前建筑的截止时间就从已经选择的建筑里扔掉耗时最长的那栋。因为扔掉耗时最长的能让总时间下降最多这样当前建筑以及后续建筑都更容易被容纳。还是拿上面的反例A 耗时 100 截止 100可以把 A 先加入sum 100没有超时。遇到 B加入后 sum 101B 的截止 101刚好不超时。遇到 C加入后 sum 102C 的截止 102也刚好。遇到 D加入后 sum 103超过了 D 的截止 103等于不算超过。这组刚好不触发后悔操作但你可以改成 A 截止 100B、C、D 截止分别是 101、102、103在加入 C 时 sum 会是 102 等于截止加入 D 时 sum 是 103 也等于截止依然不触发。说明这组数据在“恰好”边界上不会触发。把 A 的截止放宽后续截止收紧即可。总之触发后悔操作时从 A、B、C 中扔掉耗时 100 的 A剩下 B C 的总时间是 2后续 D 也能加入答案从 1 变成 4 或者至少 3。这个动态替换过程就是后悔贪心的核心。3.2 为什么用大根堆而不是小根堆堆的作用是“快速找出当前方案里耗时最长的任务”所以必须用大根堆。如果你用小根堆每次弹出的都是耗时最短的那踢掉一个短任务对总时间几乎没有缓解后续该塞不下还是塞不下贪心就退化成“每次踢掉当前刚加入的任务”等于白做。很多刚学的人会把堆和“选最小”绑定因为很多贪心题都是小根堆取最便宜的元素。但这里要记住不是堆决定了取最大还是最小而是“淘汰策略”决定了堆的形态。淘汰最耗时的用大根堆如果问题是选收益最大的 k 个工作淘汰收益最小的那就用小根堆。3.3 “弹出最大耗时”为什么不会错收益论证为什么每超时一次就弹出最大耗时最终得到的一定是最大数量这里给一个很直观的归纳论证。假设我们处理完了前 i 栋建筑堆里保存的方案是所有能用前 i 栋建筑搭出来的、总耗时最小的那个“相同数量”方案。更准确地说在数量为 k 的所有可行方案里堆里的那个方案总耗时一定不超过其他任何方案。处理第 i1 栋建筑时把它强行加进去数量变成 k1。如果总耗时不超过截止时间那么它就是当前数量 k1 下总耗时最小的候选如果总耗时超过截止时间说明任何包含这 k1 个任务的方案在这个时刻都不可行必须减少一个任务。为了让留给未来的时间最多应该去掉耗时最大的那个。去掉之后剩余 k 个任务的总耗时仍然是所有 k 个任务组合里总耗时最小的。因为如果存在另一个 k 个任务的组合总耗时更小我们完全可以在上一轮就把它放进堆里。所以整个过程中堆里始终维护的是“当前已考虑建筑内任意相同数量下总耗时最小的方案集合”。最终堆的大小就是能修的最多建筑数。这个论证不依赖复杂的交换证明理解了就能记住。4. 代码实现与关键细节C / Python 双版本4.1 C 参考代码#include bits/stdc.h using namespace std; struct Building { long long cost; long long deadline; }; bool cmp(const Building a, const Building b) { return a.deadline b.deadline; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorBuilding buildings(n); for (int i 0; i n; i) { cin buildings[i].cost buildings[i].deadline; } sort(buildings.begin(), buildings.end(), cmp); priority_queuelong long pq; // 大根堆存修理耗时 long long sum 0; // 当前方案的总耗时 for (int i 0; i n; i) { sum buildings[i].cost; pq.push(buildings[i].cost); if (sum buildings[i].deadline) { sum - pq.top(); pq.pop(); } } cout pq.size() \n; return 0; }这段代码的核心只有循环里四行加入、判断、弹出、减时间。很多人第一次看会疑惑为什么不先判断能不能加入而是先加入再看要不要弹出这正是“后悔”思想的体现——先假设它要修如果假设导致冲突再反悔。这样可以保证我们永远给当前建筑一个机会而不是草率地跳过它。4.2 Python 版本与负数取巧写法Python 的 heapq 默认是小根堆想要大根堆最简单的方法是把所有耗时取负数再入堆。每次弹出时拿到的其实是“负的最大耗时”加到 sum 上正好把对应的耗时减回去。import heapq n int(input()) buildings [] for _ in range(n): t1, t2 map(int, input().split()) buildings.append((t2, t1)) buildings.sort() pq [] sum_time 0 for deadline, cost in buildings: heapq.heappush(pq, -cost) sum_time cost if sum_time deadline: sum_time heapq.heappop(pq) print(len(pq))这里 heapq.heappop(pq) 返回的是负数比如堆里存的是 -6弹出后 sum_time (-6)等价于 sum_time - 6非常巧妙。注意不要写反是加上弹出的负数不是减掉弹出的负数。4.3 几个必须注意的实现细节第一排序必须按截止时间升序千万不要按修理耗时排。按键是 deadline不是 cost。这个错误我身边不下五个人犯过一犯就是全盘皆输。第二sum 和 cost 要开 long long。题目虽然没说极端到什么程度但 n 到 15 万每个耗时可能到 2e9总时间完全可能超过 int 范围。C 里用 int 存 sum在隐藏数据上会直接溢出成负数然后判断永远为假答案错得莫名其妙。第三判断条件是 sum deadline也就是严格大于才弹出。如果 sum 恰好等于 deadline当前建筑刚好踩着点修完不需要反悔。写成 也不会挂但会多一次无意义的弹出数据弱的时候察觉不出来数据强的时候可能 WA。第四弹出堆顶后不需要关心弹出来的是不是当前刚加入的建筑。如果当前建筑本身耗时最大弹出它就相当于放弃当前建筑这也是合理解。因为此时不放弃它就得放弃别人放弃最大耗时在数量上总是最优的。5. 现场调试实录我踩过的坑和验证方法5.1 排序方向写反答案直接崩我第一次写这道题时把 sort 的比较函数写成了return a.cost b.cost想的是“先修耗时短的”。结果样例过了一交上去全 WA。后来手造数据才发现截止时间完全被打乱后面的“后悔”操作全部建立在错误的时间线上堆维护的方案根本不可行。这个坑的隐蔽之处在于排序错的时候小数据不一定错因为后悔操作会兜底。比如只有两组数据先修谁都有可能在截止时间内完成排序方向反了也可能侥幸正确。但数据一多正确性立刻崩塌。所以写完后一定要检查排序字段或者用一组“截止时间乱序但答案唯一”的数据验证。5.2 忘记开 long long被大样例教做人还有一次我把结构体里的 cost 和 deadline 都写成 intsum 也是 int。本地小数据全过交上去有一个点直接 WA。日志里能看到 sum 变成了负数导致sum deadline永远成立疯狂弹出最后堆大小变成 0。排查办法很简单在循环里加一行调试输出看 sum 是不是出现负数或者异常大值。出现这种情况十有八九是溢出。竞赛里这类题目数据规模都是给满的不要有任何侥幸涉及累加的变量一律 long long。5.3 手造数据自测的方法这里分享一个我常用的自测技巧。不要只测样例要造几组“卡贪心”的数据一组全是截止时间很紧、耗时很短的建筑答案应该接近 n。一组第一个建筑耗时巨大但截止时间也巨大后面全是小事答案应该接近 n-1 或 n。一组每个建筑的耗时都大于等于截止时间这时候每栋建筑都只能单独修但注意如果截止时间递增可能能修多个答案是按截止排序后能修的最长序列。一组耗时相同但截止时间不断收紧验证排序边界。其中最关键的是第 2 类。它能逼出“能修就修”和“后悔贪心”的差异也是这道题最常见的考点。5.4 边界条件与极端数据的检查清单我整理了一张自测清单每次提交前照着过一遍检查项说明n 0 或 n 1程序不能崩答案分别是 0 和 1所有建筑截止时间相同此时只能按耗时从小到大选堆逻辑应等价于选最小耗时集合最大耗时 多个短任务验证是否真的会弹出最大耗时耗时和截止时间取到 2e9 附近验证 long long 是否覆盖截止时间乱序排序是否正确恢复成 EDD 序这些检查 30 秒就能跑完但能过滤掉绝大多数低级错误。我后来写所有调度类贪心题都会先套这个清单。6. 套路迁移一道题吃透一类“后悔贪心”6.1 P2949 工作调度同一套路的另一张脸有一道同样经典的题每个工作有截止时间和收益每个单位时间只能做一个工作问最多能获得多少收益。这个题表面上是“最大化收益”和我们的“最大化数量”不一样但结构惊人地相似。做法也是先按截止时间排序用小根堆维护当前已选工作的收益每当加入的工作数量超过当前截止时间能容纳的量时弹出收益最小的那个。这里堆从大根堆换成了小根堆原因仍然落在淘汰策略上我们要淘汰收益最小的给收益更大的工作腾位置。你把两道题放在一起看会发现骨架完全一样只是“要维护的关键属性”从耗时变成了收益。这个通式可以概括为扫描排序后的任务把候选塞进堆超过约束就弹出“在当前意义上最差”的那个。6.2 小Z的AK计划带距离的后悔贪心还有一类问题在“任务选择”之外加了一层位置约束比如小Z的AK计划有 n 道题分布在一条直线上每道题有位置和做题耗时小Z从起点出发移动移动要花时间做题也要花时间问在总时间限制内最多能做几道题。这类题的做法是先按位置排序枚举最远到达的题目把沿途做题耗时塞进大根堆每超时一次就扔掉耗时最长的题同时把移动时间也算进总消耗。这一步比建筑抢修多了“移动距离”这个因素但核心还是“超时则弹出最大耗时”。你会发现后悔贪心的本质是在某个资源约束下做增量选择当约束被打破时通过淘汰一个最不利元素来恢复约束。移动距离只是另一个需要计入总消耗的项而已。6.3 如何快速识别“该用后悔贪心”的题目特征我总结了三条判断标准命中两条以上就可以优先考虑这个套路。第一每个任务的收益相同或者可以拆成“数量优先”的目标。建筑抢修里每栋楼价值相同所以可以放心淘汰大耗时任务不会因为淘汰而损失更高的价值。如果每个任务价值不同淘汰时就要综合权衡可能退化成 DP。第二约束是单调递增的截止时间或者总时间限制。因为只有时间线是单调的“越往后越紧张”这个性质才能成立贪心决策才不会乱套。带位置的任务位置排序后移动耗时也是单调累加的同理。第三存在“先假设可选再后悔淘汰”的空间。判断标准就是“能修就修”的贪心会不会被一个大项堵死。如果会那大概率就是后悔贪心如果不会直接简单贪心就够了。这三条是我做题时的快速过滤器。它们不能代替证明但能帮你在一场比赛中快速找到方向。真正的严格证明还是看上一节讲的“总耗时最小集合”的归纳论证。我个人在实际刷题里最深的体会是后悔贪心不是一种“技巧”而是一种思维方式。它教你在资源紧张的时候不要急着拒绝新机会而是先看看旧选择里有没有可以优化的空间。这个思路用在日常排期上也很好使——比如这周要做的任务太多与其直接砍掉新需求不如找出上周遗留的重活、耗时最长的那个先砍掉。多留一点缓冲后面才有更多的余地。