拿到这题我第一反应是——懂了又是披着物理外衣的调度题。题目叫“物理实验”听着像要推公式、算误差、搞单位换算结果一读题面n个实验每个实验有耗时和截止时间问最多能做几个。这不就是教科书级的“带截止时间的任务调度”吗贪心解法固定套路截止时间排序 优先队列反悔。对刚学贪心的同学来说这道easy版最大的价值不是那点排序和堆的代码而是帮你彻底搞懂“贪心决策为什么可以反悔”“反悔的时候扔谁不扔谁”。本文就把这题的题面拆开、贪心思路捋直、代码逐行讲透再把我在实际做题和调错中遇到的坑全部摆出来希望能让你看完之后对这类题做到秒杀。1. 题意拆解实验安排的本质是调度1.1 题面关键词逐句解读先明确题面在说什么。大意是实验室里有n个待做实验每个实验有两个属性——截止时间d[i]和所需耗时t[i]。实验一旦开始就不能中断并且必须在截止时间之前含完成。每个实验完成得1分问最多能完成多少个实验。划重点这个模型里根本没有“物理”什么事。“截止时间”决定做实验的最后期限“耗时”决定做实验的代价“求最多完成数量”说明每个实验的价值相同。所以题目本质是一个最优化问题在时间线的约束下从n个任务里挑出一个子集使得它们能按某种顺序全部在截止时间前完成并且这个子集尽可能大。这类题有个非常经典的等价说法假设你有n场必须参加的会议每场会议有开始准备时间和最晚必须开始的时间你只能一场一场做问最多能参加几场。物理实验、考试复习、加工零件、快递配送全都是一副面孔。识别出这一点题目难度直接减半。1.2 为什么我第一眼就认定它是任务调度模型判断一个题目是不是调度模型就看三点有没有“每个任务消耗固定资源”的描述有没有“每个任务有最后期限”的描述是不是求“能完成的最大数量/最大价值”。这题三点全中。还有人会问这个模型和“活动选择问题”是不是一回事容易混淆。活动选择问题是每个活动有开始时间和结束时间活动之间不能重叠求最多选几个活动。那个题的贪心是按结束时间排序然后直接选。但本题不是时间区间而是“一个任务占用一段连续时间且必须在某个时刻前放进去”。区别在于活动选择问题中活动的开始时间固定你只能被动安排而调度模型中任务只要你选了可以放在任意合适的时刻只要保证每个任务都在自己截止时间前完成。所以本题的贪心策略和活动选择完全不同。强烈建议把两个模型放在一起对比学习防止学串。1.3 题目的数据范围与复杂度要求洛谷的easy题一般不会在数据范围上卡得太死但这不影响我们用标准思路解题。假设n最大能到十万甚至百万级别那排序堆的做法复杂度是O(n log n)稳过。如果n只有几千甚至可以直接用O(n^2)的动态规划但没必要。我写代码时习惯先看数据范围再定算法这道题一眼扫过去排序第一关键字、堆维护第二关键字复杂度瓶颈在排序上n到一百万也扛得住。2. 三种错误思路与贪心的由来2.1 按截止时间排序然后直接计数——错在哪很多新手第一眼会想既然截止时间越早的任务越紧张那就按截止时间升序排能塞就塞最后统计数量不就行了我一开始也是这么想的于是高高兴兴写完样例过了一交就WA。问题在于“能塞就塞”只考虑了任务的紧急程度没考虑任务的“体积”。举个例子现在有两个实验实验A截止时间10耗时9实验B截止时间10耗时2实验C截止时间11耗时2按截止时间排序后顺序是A、B、C。先塞A总耗时9不超10再塞B总耗时11超了于是放弃B答案变成2。但实际上最优解是选B和C先做B耗时2在第2时刻完成再做C总耗时4在第4时刻完成两个都在截止时间内答案是3。问题出在哪你让耗时9的A把两个“小任务”挤掉了而A本身并不比B、C“更值得做”。这说明一个道理贪心不能光看截止时间还得考虑任务的“体积”。截止时间紧急只是约束条件不是价值排序的标准。2.2 按耗时排序——错得更离谱那按耗时升序排先做耗时短的总数量不就多了吗这个直觉来自“装尽可能多物品”的背包问题但放在带截止时间的调度里就翻车了。还是举例子实验A截止时间100耗时1实验B截止时间2耗时2实验C截止时间3耗时1按耗时升序排A耗时1、C耗时1、B耗时2。先塞A总耗时1不超100再塞C总耗时2不超3再塞B总耗时4超了2放弃B答案2。但最优解是专心做B和C先做C耗时1第1时刻完成再做B累计耗时3恰好等于截止时间完成两个。答案是2等一下这个例子还没区分开错误方案换一个实验A截止时间100耗时1实验B截止时间10耗时10实验C截止时间10耗时1按耗时升序A、C、B。塞A总耗时1塞C总耗时2塞B总耗时12超10答案2。但最优解是C和B先做C耗时1再做B累计11不对B截止10完成B时累计时间11已经超了。最优解应该是A和B先做B耗时10完成时正好10再做A耗时1累计11不超100完成2个。按耗时升序也完成了2个……我需要构造更能区分两种排序的例子。关键在于只看耗时会忽略截止时间非常早的任务导致你优先做了一大堆“不急”的实验结果最急的那个反而没塞进去。比如实验A截止时间3耗时3实验B截止时间100耗时1按耗时升序先做B累计1再做A累计4超了A的截止3只好放弃A答案1。但显然先做A再做B两者都能完成答案2。所以按耗时排序完全错误。正确策略必须兼顾“截止时间”和“耗时”两个维度而这两个维度恰恰对应了排序和堆。2.3 正确方向给“反悔”留后路经过上面的试错你会发现一个核心矛盾截止时间早的先安排但耗时长的任务可能挤掉多个耗时短的任务耗时短的任务优先但可能耽误截止时间早的任务。两者都不完美。有没有一种策略能同时满足“截止时间早的要得到尊重”和“耗时短的尽量多留”有那就是“先按截止时间排序 逐步构建方案 允许后悔”。构建方案时每一步都先把当前任务塞进去如果发现塞不下了就回头丢掉一个“性价比最低”的任务。这个“回头丢掉”的过程就是贪心的反悔机制也是这道题的精髓。所谓“后悔药贪心”本质上是在贪心选择的同时维护一个可替换的候选集合让算法具备修正此前决策的能力。3. 正确解法截止时间排序 优先队列反悔3.1 算法流程四句话讲完这题的代码量非常短核心逻辑只要四步把所有实验按截止时间升序排序。维护一个大根堆优先队列堆里存的是“当前已选实验”的耗时。遍历每个实验先把当前实验塞进堆累计耗时加上它的耗时。如果累计耗时超过了当前实验的截止时间就从堆里弹出耗时最大的那个实验同时累计耗时减去它。最后堆里还剩多少元素答案就是多少。第一步的排序保证我们按“紧急程度”依次考虑任务越早到截止时间的实验越先被安排。第二步到第四步实现“塞不进去就扔最重的”这一反悔逻辑。3.2 为什么堆顶是“该扔”的实验一步反悔的奥义很多初学者看完流程会问“为什么超时的时候一定要扔掉耗时最大的实验为什么扔掉它一定不会让答案变差”答案藏在一个简单的事实里我们同时只能做一件事总耗时就是所有已选实验耗时的和。如果当前累计耗时超过了当前实验的截止时间说明“已选择的这些实验”不可能全部按时完成必须淘汰一个。淘汰哪个损失最小因为是求数量每个实验贡献1个名额所以从数量上看淘汰谁都一样。但从“剩余时间”上看淘汰耗时最大的实验能释放最多的时间让剩余实验更容易满足截止时间约束。一个实验占用的时间越长它未来“挤出”其他任务的可能性就越大所以优先丢它。更精妙的是被丢掉的实验也有可能是“当前这个新任务”自己。如果当前实验耗时特别大塞进去之后累计时间超了而堆顶恰好就是它自己那么弹出它就等价于“这个实验不值得做果断放弃”。这一点在实际代码中是自动发生的不需要特判。理解了这个你就理解了这道题的一半。3.3 正确性证明交换论证三板斧面试或者写题解的时候光说“显然正确”是不够的需要给出清晰证明。我习惯用三步走第一步排序按截止时间升序后任意一个可行方案都可以重排成同样符合“按截止时间升序执行”的顺序。因为如果两个任务A、B都选了且A截止时间早于B那把A排在B前面不会破坏A、B的截止时间约束。理由是交换论证A原本在后面可能晚完成把它提前只会更安全B晚一点做但A、B都能在各自截止时间前完成时交换后B的完成时间等于原来A的完成时间一定不超过B的截止时间。所以考虑排序后依次决策不会漏掉最优解。第二步贪心选择处理到第i个任务时堆里保存的是在当前“前i个任务中选择数量最多的方案”下所选任务集合且总耗时最小。这一步用数学归纳法。初始时为空满足条件。当加入第i个任务时如果累计耗时没超截止时间直接加入即可此时选择数量最多且总耗时最小显然成立。如果累计耗时超过了截止时间说明任何包含这i个任务中一部分的方案为了让数量最多必须从当前集合中拿掉一个任务。拿掉谁为了保持总耗时最小拿掉耗时最大的那一个。因为当前集合已经是数量最多、总耗时最小的方案拿掉耗时最大的任务后新集合依然是数量最多的数量减一但如果不拿则无可行方案拿掉后重新可行且总耗时在新的约束下最小。第三步归纳结论遍历完所有任务后堆中集合在全部n个任务下可行且数量最多直接输出数量。至此正确性闭环。这套证明模板不仅适用这题也适用绝大多数“排序堆反悔”类题目我强烈建议背下来。4. 代码实现与细节处理4.1 完整C代码先贴一份我自己用的代码#include bits/stdc.h using namespace std; struct Node { long long d, t; // d: 截止时间, t: 耗时 }; 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].d a[i].t; } sort(a.begin(), a.end(), [](const Node x, const Node y) { if (x.d ! y.d) return x.d y.d; return x.t y.t; // 截止时间相同时耗时短的排前面同为可选 }); priority_queuelong long pq; // 默认大根堆堆顶是耗时最长的实验 long long total 0; // 当前已选实验的总耗时 for (auto e : a) { pq.push(e.t); total e.t; if (total e.d) { total - pq.top(); pq.pop(); } } cout pq.size() \n; return 0; }这份代码的核心在循环内部只有三行塞进去、加时间、超时弹堆顶。每次弹堆顶堆里元素数量减一总耗时减去最大耗时。循环结束后堆里的元素数量就是最终能完成的实验数量。4.2 关键细节为什么用大根堆而不是小根堆优先队列默认是“大根堆”也就是堆顶存放最大值。我们每次弹出的是“耗时最长的实验”所以直接用默认的priority_queue 即可不需要任何比较器。很多人一看到“反悔”就以为要用小根堆这题恰恰相反——不是选最小留下最大而是把最大的扔掉。另外有一个容易忽略的情况如果当前实验的耗时非常大大到塞进去之后累计时间爆表堆顶就是这个实验自己那么弹出后total会减掉这个耗时相当于这个实验白塞了一轮最终没被选入。代码不需要特判这保证了逻辑的简洁。还要注意排序时截止时间相同的情况。如果两个实验截止时间相同怎么排都不影响正确性因为处理到第二个时累计耗时和截止时间约束不变堆的反悔机制会自行调节。我在代码里顺手加了耗时短的在前本身不影响结果但能稍微提高一点直觉上的合理性。4.3 手推样例看着堆一步步变化光看代码不够直观我手推一个例子。假设输入4 10 3 8 2 12 5 15 8排序后顺序为实验(8,2)、实验(10,3)、实验(12,5)、实验(15,8)。处理第1个实验截止8耗时2。塞进堆堆{2}total2不超过8不弹。此时选中实验数1。处理第2个实验截止10耗时3。塞进堆堆{3,2}total5不超过10不弹。选中实验数2。处理第3个实验截止12耗时5。塞进堆堆{5,3,2}total10不超过12不弹。选中实验数3。处理第4个实验截止15耗时8。塞进堆堆{8,5,3,2}total18超过15。弹出堆顶8total变成10堆{5,3,2}。选中实验数3。最终答案3。最优方案做(8,2)、(10,3)、(12,5)三个实验总耗时10在截止时间内全部完成而(15,8)因为耗时太长被放弃。如果反向思考这个例子直观地展示了“淘汰最大”的好处扔掉耗时8的立刻腾出8个单位的空闲时间三个小任务全部保住。5. 踩坑实录那些WA了半天的点5.1 排序第一关键字写成耗时我见过最多的错误是把实验按耗时升序排序然后套同样的堆逻辑。结果就是前面分析的“先做了一堆轻松的结果紧急任务被耽误”。请记住这题必须按截止时间升序排序因为截止时间决定了任务的紧迫底线耗时只参与反悔时的淘汰决策。5.2 判定条件写成塞之前判断能不能加有人喜欢用“塞之前先判断”的写法if (total e.t e.d) { total e.t; pq.push(e.t); } else { // 尝试替换掉堆顶 }这种写法也不是不行但容易在“替换”分支里忘记更新total或者忘记把当前任务压进堆。相比之下我的“先塞后弹”写法更不容易漏逻辑反正塞进去超时弹出最大代码统一。如果你是新手我推荐直接采用“先塞后弹”。5.3 堆里存的是截止时间而不是耗时有个学弟调试了很久最后发现他把堆里压的是e.d截止时间。这会导致弹堆顶时弹掉“截止时间最晚”的实验而不是耗时最长的实验结果完全不对。堆里存的一定是耗时t[i]因为它代表任务占用的资源量截止时间只是用来判断是否超时不是用来比较“谁该被淘汰”的标准。5.4 数据溢出问题题目数据范围如果给到1e9甚至更大int就会爆。total是很多个耗时累加的结果n到十万时total完全可能超过int范围。我建议直接无脑开long long反正内存也就多几个字节省去后期Debug溢出的痛苦。优先队列里的元素类型也保持一致用long long。5.5 常见问题速查表故障现象可能原因解决方式样例通过但交题WA排序关键字错误检查sort的lambda确认按d升序输出值偏大超时后没有弹堆顶确认每次total e.d时执行了pop输出值偏小替换逻辑漏push推荐改成先塞后弹统一写法答案全错堆里存了截止时间检查pq.push的实参是否是e.t部分数据WAtotal类型为int溢出全部换成long long输入超时没有关闭同步加ios::sync_with_stdio(false)6. 从物理实验到一类题变形不止一种6.1 加权版每个实验价值不同如果题目改成“完成第i个实验获得v[i]的价值求最大总价值”算法就要微调。这时候反悔时淘汰谁不再看“耗时最长”而是看“价值最小”。因为数量固定时总价值最大化淘汰价值最小的任务损失最小。做法变成按截止时间排序后用小根堆维护已选实验的价值如果累计耗时超了截止时间弹出价值最小的实验。这就是另一道经典题的解法很多新手会认为物理实验这题是加权版的简化版其实方向反了本题每个实验价值等于1反悔规则退化为“淘汰耗时最长”。6.2 变体截止时间换成最晚开始时间还有类似的题每个任务告诉你“最晚开始时间”而不是截止时间。模型其实可以转化最晚开始时间耗时最晚完成时间所以可以先把每个任务换算成完成截止时间再用原做法。转化的思维比死记题更重要。6.3 变体要求输出具体方案输出方案时可以再开一个数组记录每个实验是否被选中。在弹出堆顶时把该实验的标记清掉最后遍历一遍堆里的元素输出标记即可。注意不能只记录“最终堆中的实验”因为堆里存的是耗时没有下标信息所以如果题目要求输出ID就得自己再维护一个存ID的堆或者在push时额外记住对应下标。我实战时一般用pairlong long, int压堆耗时放第一关键字下标放第二关键字。6.4 同类模型怎么积累这类“排序堆反悔”的题目在竞赛里一抓一大把核心套路就是遇到“有时间限制求最大数量/价值”的题先想能不能按某个关键字的截止时间排序再用堆维护候选集合超限就反悔。一道题做熟之后做它的加权版、变式题都会顺手很多。以我个人经验这类题最值得投入时间的不是背代码而是搞懂“为什么反悔掉最大的/最小的能保证答案不劣”。一旦你把这个道理用自己的话复述清楚它就会从一道题的解法变成一类题的直觉。我在教某学弟的时候发现他卡了很久不是因为不会写堆而是始终觉得“反悔”是玄学。后来我让他把每个任务想成一件行李截止时间是登机时间总耗时是背包容量超重时你肯定会扔最重的那件他一下就想通了。希望这篇详细的拆解也能帮你捅破这层窗户纸。
拿到这题我第一反应是——懂了又是披着物理外衣的调度题。题目叫“物理实验”听着像要推公式、算误差、搞单位换算结果一读题面n个实验每个实验有耗时和截止时间问最多能做几个。这不就是教科书级的“带截止时间的任务调度”吗贪心解法固定套路截止时间排序 优先队列反悔。对刚学贪心的同学来说这道easy版最大的价值不是那点排序和堆的代码而是帮你彻底搞懂“贪心决策为什么可以反悔”“反悔的时候扔谁不扔谁”。本文就把这题的题面拆开、贪心思路捋直、代码逐行讲透再把我在实际做题和调错中遇到的坑全部摆出来希望能让你看完之后对这类题做到秒杀。1. 题意拆解实验安排的本质是调度1.1 题面关键词逐句解读先明确题面在说什么。大意是实验室里有n个待做实验每个实验有两个属性——截止时间d[i]和所需耗时t[i]。实验一旦开始就不能中断并且必须在截止时间之前含完成。每个实验完成得1分问最多能完成多少个实验。划重点这个模型里根本没有“物理”什么事。“截止时间”决定做实验的最后期限“耗时”决定做实验的代价“求最多完成数量”说明每个实验的价值相同。所以题目本质是一个最优化问题在时间线的约束下从n个任务里挑出一个子集使得它们能按某种顺序全部在截止时间前完成并且这个子集尽可能大。这类题有个非常经典的等价说法假设你有n场必须参加的会议每场会议有开始准备时间和最晚必须开始的时间你只能一场一场做问最多能参加几场。物理实验、考试复习、加工零件、快递配送全都是一副面孔。识别出这一点题目难度直接减半。1.2 为什么我第一眼就认定它是任务调度模型判断一个题目是不是调度模型就看三点有没有“每个任务消耗固定资源”的描述有没有“每个任务有最后期限”的描述是不是求“能完成的最大数量/最大价值”。这题三点全中。还有人会问这个模型和“活动选择问题”是不是一回事容易混淆。活动选择问题是每个活动有开始时间和结束时间活动之间不能重叠求最多选几个活动。那个题的贪心是按结束时间排序然后直接选。但本题不是时间区间而是“一个任务占用一段连续时间且必须在某个时刻前放进去”。区别在于活动选择问题中活动的开始时间固定你只能被动安排而调度模型中任务只要你选了可以放在任意合适的时刻只要保证每个任务都在自己截止时间前完成。所以本题的贪心策略和活动选择完全不同。强烈建议把两个模型放在一起对比学习防止学串。1.3 题目的数据范围与复杂度要求洛谷的easy题一般不会在数据范围上卡得太死但这不影响我们用标准思路解题。假设n最大能到十万甚至百万级别那排序堆的做法复杂度是O(n log n)稳过。如果n只有几千甚至可以直接用O(n^2)的动态规划但没必要。我写代码时习惯先看数据范围再定算法这道题一眼扫过去排序第一关键字、堆维护第二关键字复杂度瓶颈在排序上n到一百万也扛得住。2. 三种错误思路与贪心的由来2.1 按截止时间排序然后直接计数——错在哪很多新手第一眼会想既然截止时间越早的任务越紧张那就按截止时间升序排能塞就塞最后统计数量不就行了我一开始也是这么想的于是高高兴兴写完样例过了一交就WA。问题在于“能塞就塞”只考虑了任务的紧急程度没考虑任务的“体积”。举个例子现在有两个实验实验A截止时间10耗时9实验B截止时间10耗时2实验C截止时间11耗时2按截止时间排序后顺序是A、B、C。先塞A总耗时9不超10再塞B总耗时11超了于是放弃B答案变成2。但实际上最优解是选B和C先做B耗时2在第2时刻完成再做C总耗时4在第4时刻完成两个都在截止时间内答案是3。问题出在哪你让耗时9的A把两个“小任务”挤掉了而A本身并不比B、C“更值得做”。这说明一个道理贪心不能光看截止时间还得考虑任务的“体积”。截止时间紧急只是约束条件不是价值排序的标准。2.2 按耗时排序——错得更离谱那按耗时升序排先做耗时短的总数量不就多了吗这个直觉来自“装尽可能多物品”的背包问题但放在带截止时间的调度里就翻车了。还是举例子实验A截止时间100耗时1实验B截止时间2耗时2实验C截止时间3耗时1按耗时升序排A耗时1、C耗时1、B耗时2。先塞A总耗时1不超100再塞C总耗时2不超3再塞B总耗时4超了2放弃B答案2。但最优解是专心做B和C先做C耗时1第1时刻完成再做B累计耗时3恰好等于截止时间完成两个。答案是2等一下这个例子还没区分开错误方案换一个实验A截止时间100耗时1实验B截止时间10耗时10实验C截止时间10耗时1按耗时升序A、C、B。塞A总耗时1塞C总耗时2塞B总耗时12超10答案2。但最优解是C和B先做C耗时1再做B累计11不对B截止10完成B时累计时间11已经超了。最优解应该是A和B先做B耗时10完成时正好10再做A耗时1累计11不超100完成2个。按耗时升序也完成了2个……我需要构造更能区分两种排序的例子。关键在于只看耗时会忽略截止时间非常早的任务导致你优先做了一大堆“不急”的实验结果最急的那个反而没塞进去。比如实验A截止时间3耗时3实验B截止时间100耗时1按耗时升序先做B累计1再做A累计4超了A的截止3只好放弃A答案1。但显然先做A再做B两者都能完成答案2。所以按耗时排序完全错误。正确策略必须兼顾“截止时间”和“耗时”两个维度而这两个维度恰恰对应了排序和堆。2.3 正确方向给“反悔”留后路经过上面的试错你会发现一个核心矛盾截止时间早的先安排但耗时长的任务可能挤掉多个耗时短的任务耗时短的任务优先但可能耽误截止时间早的任务。两者都不完美。有没有一种策略能同时满足“截止时间早的要得到尊重”和“耗时短的尽量多留”有那就是“先按截止时间排序 逐步构建方案 允许后悔”。构建方案时每一步都先把当前任务塞进去如果发现塞不下了就回头丢掉一个“性价比最低”的任务。这个“回头丢掉”的过程就是贪心的反悔机制也是这道题的精髓。所谓“后悔药贪心”本质上是在贪心选择的同时维护一个可替换的候选集合让算法具备修正此前决策的能力。3. 正确解法截止时间排序 优先队列反悔3.1 算法流程四句话讲完这题的代码量非常短核心逻辑只要四步把所有实验按截止时间升序排序。维护一个大根堆优先队列堆里存的是“当前已选实验”的耗时。遍历每个实验先把当前实验塞进堆累计耗时加上它的耗时。如果累计耗时超过了当前实验的截止时间就从堆里弹出耗时最大的那个实验同时累计耗时减去它。最后堆里还剩多少元素答案就是多少。第一步的排序保证我们按“紧急程度”依次考虑任务越早到截止时间的实验越先被安排。第二步到第四步实现“塞不进去就扔最重的”这一反悔逻辑。3.2 为什么堆顶是“该扔”的实验一步反悔的奥义很多初学者看完流程会问“为什么超时的时候一定要扔掉耗时最大的实验为什么扔掉它一定不会让答案变差”答案藏在一个简单的事实里我们同时只能做一件事总耗时就是所有已选实验耗时的和。如果当前累计耗时超过了当前实验的截止时间说明“已选择的这些实验”不可能全部按时完成必须淘汰一个。淘汰哪个损失最小因为是求数量每个实验贡献1个名额所以从数量上看淘汰谁都一样。但从“剩余时间”上看淘汰耗时最大的实验能释放最多的时间让剩余实验更容易满足截止时间约束。一个实验占用的时间越长它未来“挤出”其他任务的可能性就越大所以优先丢它。更精妙的是被丢掉的实验也有可能是“当前这个新任务”自己。如果当前实验耗时特别大塞进去之后累计时间超了而堆顶恰好就是它自己那么弹出它就等价于“这个实验不值得做果断放弃”。这一点在实际代码中是自动发生的不需要特判。理解了这个你就理解了这道题的一半。3.3 正确性证明交换论证三板斧面试或者写题解的时候光说“显然正确”是不够的需要给出清晰证明。我习惯用三步走第一步排序按截止时间升序后任意一个可行方案都可以重排成同样符合“按截止时间升序执行”的顺序。因为如果两个任务A、B都选了且A截止时间早于B那把A排在B前面不会破坏A、B的截止时间约束。理由是交换论证A原本在后面可能晚完成把它提前只会更安全B晚一点做但A、B都能在各自截止时间前完成时交换后B的完成时间等于原来A的完成时间一定不超过B的截止时间。所以考虑排序后依次决策不会漏掉最优解。第二步贪心选择处理到第i个任务时堆里保存的是在当前“前i个任务中选择数量最多的方案”下所选任务集合且总耗时最小。这一步用数学归纳法。初始时为空满足条件。当加入第i个任务时如果累计耗时没超截止时间直接加入即可此时选择数量最多且总耗时最小显然成立。如果累计耗时超过了截止时间说明任何包含这i个任务中一部分的方案为了让数量最多必须从当前集合中拿掉一个任务。拿掉谁为了保持总耗时最小拿掉耗时最大的那一个。因为当前集合已经是数量最多、总耗时最小的方案拿掉耗时最大的任务后新集合依然是数量最多的数量减一但如果不拿则无可行方案拿掉后重新可行且总耗时在新的约束下最小。第三步归纳结论遍历完所有任务后堆中集合在全部n个任务下可行且数量最多直接输出数量。至此正确性闭环。这套证明模板不仅适用这题也适用绝大多数“排序堆反悔”类题目我强烈建议背下来。4. 代码实现与细节处理4.1 完整C代码先贴一份我自己用的代码#include bits/stdc.h using namespace std; struct Node { long long d, t; // d: 截止时间, t: 耗时 }; 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].d a[i].t; } sort(a.begin(), a.end(), [](const Node x, const Node y) { if (x.d ! y.d) return x.d y.d; return x.t y.t; // 截止时间相同时耗时短的排前面同为可选 }); priority_queuelong long pq; // 默认大根堆堆顶是耗时最长的实验 long long total 0; // 当前已选实验的总耗时 for (auto e : a) { pq.push(e.t); total e.t; if (total e.d) { total - pq.top(); pq.pop(); } } cout pq.size() \n; return 0; }这份代码的核心在循环内部只有三行塞进去、加时间、超时弹堆顶。每次弹堆顶堆里元素数量减一总耗时减去最大耗时。循环结束后堆里的元素数量就是最终能完成的实验数量。4.2 关键细节为什么用大根堆而不是小根堆优先队列默认是“大根堆”也就是堆顶存放最大值。我们每次弹出的是“耗时最长的实验”所以直接用默认的priority_queue 即可不需要任何比较器。很多人一看到“反悔”就以为要用小根堆这题恰恰相反——不是选最小留下最大而是把最大的扔掉。另外有一个容易忽略的情况如果当前实验的耗时非常大大到塞进去之后累计时间爆表堆顶就是这个实验自己那么弹出后total会减掉这个耗时相当于这个实验白塞了一轮最终没被选入。代码不需要特判这保证了逻辑的简洁。还要注意排序时截止时间相同的情况。如果两个实验截止时间相同怎么排都不影响正确性因为处理到第二个时累计耗时和截止时间约束不变堆的反悔机制会自行调节。我在代码里顺手加了耗时短的在前本身不影响结果但能稍微提高一点直觉上的合理性。4.3 手推样例看着堆一步步变化光看代码不够直观我手推一个例子。假设输入4 10 3 8 2 12 5 15 8排序后顺序为实验(8,2)、实验(10,3)、实验(12,5)、实验(15,8)。处理第1个实验截止8耗时2。塞进堆堆{2}total2不超过8不弹。此时选中实验数1。处理第2个实验截止10耗时3。塞进堆堆{3,2}total5不超过10不弹。选中实验数2。处理第3个实验截止12耗时5。塞进堆堆{5,3,2}total10不超过12不弹。选中实验数3。处理第4个实验截止15耗时8。塞进堆堆{8,5,3,2}total18超过15。弹出堆顶8total变成10堆{5,3,2}。选中实验数3。最终答案3。最优方案做(8,2)、(10,3)、(12,5)三个实验总耗时10在截止时间内全部完成而(15,8)因为耗时太长被放弃。如果反向思考这个例子直观地展示了“淘汰最大”的好处扔掉耗时8的立刻腾出8个单位的空闲时间三个小任务全部保住。5. 踩坑实录那些WA了半天的点5.1 排序第一关键字写成耗时我见过最多的错误是把实验按耗时升序排序然后套同样的堆逻辑。结果就是前面分析的“先做了一堆轻松的结果紧急任务被耽误”。请记住这题必须按截止时间升序排序因为截止时间决定了任务的紧迫底线耗时只参与反悔时的淘汰决策。5.2 判定条件写成塞之前判断能不能加有人喜欢用“塞之前先判断”的写法if (total e.t e.d) { total e.t; pq.push(e.t); } else { // 尝试替换掉堆顶 }这种写法也不是不行但容易在“替换”分支里忘记更新total或者忘记把当前任务压进堆。相比之下我的“先塞后弹”写法更不容易漏逻辑反正塞进去超时弹出最大代码统一。如果你是新手我推荐直接采用“先塞后弹”。5.3 堆里存的是截止时间而不是耗时有个学弟调试了很久最后发现他把堆里压的是e.d截止时间。这会导致弹堆顶时弹掉“截止时间最晚”的实验而不是耗时最长的实验结果完全不对。堆里存的一定是耗时t[i]因为它代表任务占用的资源量截止时间只是用来判断是否超时不是用来比较“谁该被淘汰”的标准。5.4 数据溢出问题题目数据范围如果给到1e9甚至更大int就会爆。total是很多个耗时累加的结果n到十万时total完全可能超过int范围。我建议直接无脑开long long反正内存也就多几个字节省去后期Debug溢出的痛苦。优先队列里的元素类型也保持一致用long long。5.5 常见问题速查表故障现象可能原因解决方式样例通过但交题WA排序关键字错误检查sort的lambda确认按d升序输出值偏大超时后没有弹堆顶确认每次total e.d时执行了pop输出值偏小替换逻辑漏push推荐改成先塞后弹统一写法答案全错堆里存了截止时间检查pq.push的实参是否是e.t部分数据WAtotal类型为int溢出全部换成long long输入超时没有关闭同步加ios::sync_with_stdio(false)6. 从物理实验到一类题变形不止一种6.1 加权版每个实验价值不同如果题目改成“完成第i个实验获得v[i]的价值求最大总价值”算法就要微调。这时候反悔时淘汰谁不再看“耗时最长”而是看“价值最小”。因为数量固定时总价值最大化淘汰价值最小的任务损失最小。做法变成按截止时间排序后用小根堆维护已选实验的价值如果累计耗时超了截止时间弹出价值最小的实验。这就是另一道经典题的解法很多新手会认为物理实验这题是加权版的简化版其实方向反了本题每个实验价值等于1反悔规则退化为“淘汰耗时最长”。6.2 变体截止时间换成最晚开始时间还有类似的题每个任务告诉你“最晚开始时间”而不是截止时间。模型其实可以转化最晚开始时间耗时最晚完成时间所以可以先把每个任务换算成完成截止时间再用原做法。转化的思维比死记题更重要。6.3 变体要求输出具体方案输出方案时可以再开一个数组记录每个实验是否被选中。在弹出堆顶时把该实验的标记清掉最后遍历一遍堆里的元素输出标记即可。注意不能只记录“最终堆中的实验”因为堆里存的是耗时没有下标信息所以如果题目要求输出ID就得自己再维护一个存ID的堆或者在push时额外记住对应下标。我实战时一般用pairlong long, int压堆耗时放第一关键字下标放第二关键字。6.4 同类模型怎么积累这类“排序堆反悔”的题目在竞赛里一抓一大把核心套路就是遇到“有时间限制求最大数量/价值”的题先想能不能按某个关键字的截止时间排序再用堆维护候选集合超限就反悔。一道题做熟之后做它的加权版、变式题都会顺手很多。以我个人经验这类题最值得投入时间的不是背代码而是搞懂“为什么反悔掉最大的/最小的能保证答案不劣”。一旦你把这个道理用自己的话复述清楚它就会从一道题的解法变成一类题的直觉。我在教某学弟的时候发现他卡了很久不是因为不会写堆而是始终觉得“反悔”是玄学。后来我让他把每个任务想成一件行李截止时间是登机时间总耗时是背包容量超重时你肯定会扔最重的那件他一下就想通了。希望这篇详细的拆解也能帮你捅破这层窗户纸。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
