拿到这题，我第一反应是——懂了，又是披着物理外衣的调度题。题目叫“物理实验”，听着像要推公式、算误差、搞单位换算，结果一读题面，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; vector<Node> 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_queue<long 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}，total=2，不超过8，不弹。此时选中实验数1。处理第2个实验：截止10耗时3。塞进堆，堆={3,2}，total=5，不超过10，不弹。选中实验数2。处理第3个实验：截止12耗时5。塞进堆，堆={5,3,2}，total=10，不超过12，不弹。选中实验数3。处理第4个实验：截止15耗时8。塞进堆，堆={8,5,3,2}，total=18，超过15。弹出堆顶8，total变成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时额外记住对应下标。我实战时一般用pair<long 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; vector<Node> 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_queue<long 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}，total=2，不超过8，不弹。此时选中实验数1。处理第2个实验：截止10耗时3。塞进堆，堆={3,2}，total=5，不超过10，不弹。选中实验数2。处理第3个实验：截止12耗时5。塞进堆，堆={5,3,2}，total=10，不超过12，不弹。选中实验数3。处理第4个实验：截止15耗时8。塞进堆，堆={8,5,3,2}，total=18，超过15。弹出堆顶8，total变成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时额外记住对应下标。我实战时一般用pair<long long, int>压堆，耗时放第一关键字，下标放第二关键字。6.4 同类模型怎么积累这类“排序+堆反悔”的题目在竞赛里一抓一大把，核心套路就是：遇到“有时间限制，求最大数量/价值”的题，先想能不能按某个关键字的截止时间排序，再用堆维护候选集合，超限就反悔。一道题做熟之后，做它的加权版、变式题都会顺手很多。以我个人经验，这类题最值得投入时间的不是背代码，而是搞懂“为什么反悔掉最大的/最小的能保证答案不劣”。一旦你把这个道理用自己的话复述清楚，它就会从一道题的解法，变成一类题的直觉。我在教某学弟的时候发现，他卡了很久不是因为不会写堆，而是始终觉得“反悔”是玄学。后来我让他把每个任务想成一件行李，截止时间是登机时间，总耗时是背包容量，超重时你肯定会扔最重的那件，他一下就想通了。希望这篇详细的拆解，也能帮你捅破这层窗户纸。