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