聊一道洛谷的 P3619《魔法》。这题名字听起来像奇幻小说，实际拆开一看，是一道非常经典的贪心排序题。题面不绕，数据范围也不算吓人，但能做对的人绕不开一个核心问题：你知道该按什么顺序处理这些任务吗。
这道题非常适合正在积累“任务调度类”套路的人，也适合刚学完结构体排序、想拿一道不算水的题练手的选手。代码量很小，不考高级数据结构，也不需要线段树、平衡树这些东西。你只要把排序规则想清楚，整个题就是十来分钟的事；想不清楚，写一晚上也照样WA。
我用 C++ 写完了整个过程，也把排序规则的证明过程重新推了一遍。这篇就当一份记录，把题目拆开、把贪心思路讲透、把代码和踩坑点都列出来，给准备信奥或者自己在刷题的同学做个参考。
1. 题目到底在问什么
1.1 题意和输入输出
先按我自己的理解复述一遍。你现在有 Z 单位的时间，面前有 N 件事。每件事有两个属性：完成它需要 t_i 时间，完成后你会得到 b_i 时间的“奖励”。注意，这里的 b_i 是带符号的，正数表示做完后时间变多，负数表示做完后时间被扣掉。
判断能不能通过某种合理的顺序，把所有任务全部完成。如果能，输出 Yes；不能，输出 No。
输入是多组数据，第一行是数据组数，接下来每组第一行是 N 和 Z，后面 N 行是 t_i 和 b_i。这题我印象里 N 的范围不大，但多组数据叠加起来，复杂度也不能乱来。
这类题最关键的一点是：任务的完成顺序由你决定，而不是按输入顺序强制执行。很多第一次接触的同学会以为题目问的是“按给定顺序能不能完成”，那就把题目理解窄了。它真正的难点在于，你要在可以自由排序的前提下，判断是否存在一种可行方案。
1.2 为什么全排列思路行不通
最朴素的想法当然是枚举所有排列顺序，逐个检查。
N 很小的时候这思路没问题，比如 N=5，全排列才 120 种。但 N 稍大一点，比如 N=15，15! 已经是 1.3 万亿种，直接爆炸。信奥题不会给你留这种后门，所以必须找到一种确定的、不依赖于枚举的贪心规则。
我一开始也想过 DFS 剪枝，毕竟看起来每个任务只有“做”和“不做”，但题目要求的是全部做完，不是求最大值，剪枝空间很小，照样跑不动。正确方向应该是排序 + 线性扫描。
这类题有个通用直觉：如果每个任务执行的代价是固定的、收益也是固定的，那么最优顺序一般可以靠“交换相邻两个任务”来证明出来。这就是贪心里的交换论证法，也是这道题真正的灵魂。
2. 贪心策略的核心设计
2.1 先把正收益任务做完
把任务按 b_i 的正负分成两组：b_i >= 0 的是一组，b_i < 0 的是另一组。按理说，正收益任务应该是“越早做越好”，因为做完它，你的时间会变多，后面做什么都更宽裕。
但你仔细想一下，正收益任务内部也有顺序问题。如果两个任务做完都是涨时间的，那先做哪一个更合理？答案是先做 t 小的。原因很直接：做耗时短的任务，时间门槛低，更容易满足；做完之后时间变多，再去做耗时长的任务就更稳妥。反过来，如果先做耗时长的，可能当前时间不够直接失败；即使够，做完后剩余时间也不如先做短任务时那么健康。
所以正收益组内部按 t_i 升序排序。这个排序规则比较直观，也是大多数人的第一反应。但真正决定这题难度的是另一组。
2.2 负收益任务：决定生死的是“做完后还剩多少”
b_i 是负数的任务，做完会扣时间。处理这种任务的策略和正收益组正好相反：不能单纯按 t 排序，也不能单纯按 b 排序，得看两个属性的组合。
举个例子。任务 A 需要时间 3，做完扣时间 1；任务 B 需要时间 2，做完扣时间 3。先做哪个？
如果你当前时间是 3，先做 A，3 够了，做完剩 2，再做 B 也够。如果先做 B，3 也够，但做完剩 0，A 需要 3，直接失败。这俩任务的 t 和 b 都不太一样，但明显先做 A 更优。
但你再看另一组：任务 C 需要时间 5，做完扣时间 1；任务 D 需要时间 4，做完扣时间 0.5。你得比较“做完这个任务后，剩余时间还够不够做下一个”。所以真正决定顺序的，不是 t 单独的值，也不是 b 单独的值，而是 t + b 这个整体值。因为做完任务后的剩余时间就是当前时间 + b，等价于你完成这个任务之后还“剩下”多少可用空间。
2.3 排序规则的数学推导
假设两个负收益任务 i 和 j，当前时间为 cur。如果先做 i 再做 j，可行性条件是：
- cur >= t_i（做 i 之前时间要够）
- cur + b_i >= t_j（做完 i 后剩余时间要够做 j）
考虑到 b_i 是负数，第二个条件等价于 cur >= t_j - b_i。
反过来，先做 j 再做 i 的可行性条件是：
- cur >= t_j
- cur >= t_i - b_j
现在比较两个门槛。先做 i 再做 j 需要 cur 超过 max(t_i, t_j - b_i)；先做 j 再做 i 需要 cur 超过 max(t_j, t_i - b_j)。
如果想让“i 在前”这个顺序在任何可行的场景下都不比“j 在前”差，甚至更好，就需要保证 t_j - b_i <= t_i - b_j。整理一下：
- t_j + b_j <= t_i + b_i
这个式子说明什么？说明 t_i + b_i 大的任务应该排在前面。因为两个任务做完后的“剩余时间”分别是 cur + b_i 和 cur + b_j，本质上我们希望在连续处理扣时间任务时，先做那个做完后剩余时间更多的任务，这样就给后面留出更多缓冲。
所以负收益组内部的排序规则是：按 t + b 降序。
2.4 用一个小例子感受排序差异
我用一组简化数据来演示这个排序的重要性：
两个任务：
- 任务 A：t = 2，b = -1
- 任务 B：t = 1，b = -2
初始时间 cur = 3。
按 t + b 降序排序：A 的 t + b = 1，B 的 t + b = -1，所以先做 A。cur >= 2，做 A，剩余 2 单位，再做 B，2 >= 1，完成，剩余 1。成功。
如果按 t 升序排序，就会先做 B。cur >= 1，做 B，剩余 1 单位，再做 A，1 < 2，失败。这里就能看出排序规则选错，答案直接从 Yes 变成 No。
这组数据很小，但它把“做完后还剩多少”的决定性作用表现得非常清楚。
3. C++实现与完整代码
3.1 结构体定义与比较函数
这道题核心代码非常简单，一个结构体存 t 和 b 就够。排序的时候用自定义比较函数，注意正收益和负收益要分别写两个比较规则。
我习惯把cmpPos和cmpNeg分开写，这样逻辑清晰，后面排错也方便。有同学喜欢用一个比较函数配合标志位处理，也可以，但我觉得分开写更直白。
比较函数要注意返回值的含义：true表示第一个参数应该排在第二个参数前面。正收益组就是a.t < b.t；负收益组就是a.t + a.b > b.t + b.b，注意是大于号，别写成小于号。
结构体本身不需要重载运算符，两行代码就够用。有些题解会给结构体写构造函数，但这里完全没必要，C++11 之后直接用花括号初始化{t, b}就行。
3.2 主流程逻辑
整体流程分成四步：
- 读入当前时间 cur。
- 对每个任务判断 b 的正负，分别存进两个 vector。
- 正收益组按 t 升序排序，负收益组按 t + b 降序排序。
- 先遍历正收益组，再遍历负收益组，过程中如果 cur 小于当前任务的 t，直接判定失败。
遍历的时候注意一点：如果某个任务做完了，时间变成负数，不要马上 panic。后续遍历中 cur 小于任何 t 都会触发失败，所以逻辑上没问题。但如果你想知道具体的失败点，也可以在循环里加一个 if (cur < 0) 提前 break。
3.3 完整可运行代码
#include <bits/stdc++.h> using namespace std; struct Task { long long t; long long b; }; bool cmpPos(const Task& a, const Task& b) { return a.t < b.t; } bool cmpNeg(const Task& a, const Task& b) { return a.t + a.b > b.t + b.b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; long long cur; cin >> n >> cur; vector<Task> pos, neg; for (int i = 0; i < n; i++) { long long t, b; cin >> t >> b; if (b >= 0) { pos.push_back({t, b}); } else { neg.push_back({t, b}); } } sort(pos.begin(), pos.end(), cmpPos); sort(neg.begin(), neg.end(), cmpNeg); bool ok = true; for (const Task& task : pos) { if (cur < task.t) { ok = false; break; } cur += task.b; } if (ok) { for (const Task& task : neg) { if (cur < task.t) { ok = false; break; } cur += task.b; } } cout << (ok ? "Yes" : "No") << '\n'; } return 0; }这段代码在洛谷上可以直接跑，编译选项用默认的 C++17 就行。头文件直接写万能头bits/stdc++.h，省事，信奥环境里普遍支持。
3.4 自测数据与手推过程
我写代码的时候一般会带三组自测数据，全过一遍再提交，这里也分享出来。
第一组，能区分正负排序规则的：
1 2 3 2 -1 1 -2按规则先做 (2, -1)，成功，输出 Yes。
第二组，正收益任务混合的情况：
1 2 5 6 10 1 2正收益组两个任务 (6, 10) 和 (1, 2)，按 t 升序先做 (1, 2)，时间从 5 变 7，再做 (6, 10)，成功，输出 Yes。如果顺序反过来，先做 (6, 10)，5 < 6 直接失败。
第三组，无论如何都失败的情况：
1 2 3 2 -1 3 -2两个负收益任务 t + b 都是 1，先做哪个都会导致剩余时间不够做下一个，输出 No。
这三组数据覆盖了核心分支，提交前至少能帮你拦住一半的低级错误。
4. 常见错误与排查技巧
4.1 排序条件写反
我敢说这道题的大部分 WA 都出在负收益任务的排序上。有人按 b 升序，有人按 t 升序，还有人按 t + b 升序，全都会在某些数据上翻车。
判断排序是否正确，最简单的方法就是回到交换论证：假设两个相邻任务顺序可交换，交换前后的可行性条件必须比较出来。如果推导出的结论是“t + b 大的先做”，那就老老实实用>。不要凭直觉猜，不要因为上一道题的排序恰好是升序就套过来。
我自己的习惯是，每次写完排序规则，都会拿一个只有两个负收益任务的小数据手动推一遍。推完再上代码，比反复提交试错省时间得多。
4.2 b == 0 的处理
题目里 b 可能是负数，也可能是正数，还可能恰好等于 0。这个边界情况虽然小，但处理不好会影响排序逻辑。
我建议把 b >= 0 都归入正收益组。原因是 b = 0 不会改变当前时间，它对后续任务没有“增益”也没有“损耗”，排序规则无关紧要，只要确保当前时间够用就行。把它归入正收益组，按 t 升序处理，逻辑上是严格的，代码上也省一个分支。
如果你非要单独开一组，那就要额外处理它的排序，没有必要。
4.3 数据类型与多组数据
b 是负数的时候，cur 在累加过程中可能会变小，甚至变成负数。如果题目数据范围比较大，中间结果可能超过 int 的范围。为了避免这种莫名其妙的溢出，直接用long long存 t、b 和 cur。
多组数据时还有一个隐蔽的问题：如果上一组的某个标志位没重置，或者 vector 没清空，就会把上一组的脏数据带进来。上面代码里 pos 和 neg 在 while 循环内部定义，每次循环自动重新构造，就不会有这个问题。如果你习惯在循环外定义 vector，记得在每组数据开头 clear 一下。
我见过有人把 cur 声明成 int，然后把题目数据范围看岔，结果中间溢出变成负数，最后 WA 得一头雾水。这种错误最冤，但也最好避免，无脑 long long 就完事。
4.4 从 WA 结果反向定位问题
如果你提交之后 WA 了，不要急着加随机数据瞎测。先按下面这个顺序检查：
- 是不是输出格式问题。这题输出 Yes/No，注意大小写和换行。有时候题目要求首字母大写，有时候要求全小写，看清题干。
- 是不是排序规则反了。用两个负收益任务的小数据手推。
- 是不是 b = 0 放错组了。
- 是不是多组数据之间变量没清干净。
- 是不是比较函数写成
a.t + a.b < b.t + b.b了。我特意加粗这行，因为这个错误极其隐蔽，自己看代码看不出来，非得推样例才能发现。
如果你是第一次接触交换论证法，建议亲手把 2.3 节那个不等式推一遍，比看十篇题解都管用。贪心题最怕的就是“感觉应该这样排”，感觉是不可靠的，只有推导才是可靠的。
5. 这类题在竞赛里的识别与扩展
5.1 任务调度题的通用模型
P3619 只是任务调度家族里的一题。这个家族的特征非常明显：有一堆任务，每个任务有耗时，有收益；收益可能增加资源，也可能消耗资源；问能不能全部完成，或者问最多完成几个。
这类题的第一步永远是找排序规则。排序规则通常不是单看某个属性，而是看两个属性的组合。P3619 看的是 t + b，之前的很多经典题看的是“截止时间”，还有的看“所需时间 + 收益”的比值。
一个很实用的排错思路：当你写出一个排序规则后，就构造两个相邻任务，假装它们顺序可以交换，验证一下交换后是否变差。如果变差，说明当前规则正确；如果不确定，就用不等式推一遍。这个验证过程其实是很多竞赛选手下意识在做的，只是没有明确说出来。
5.2 与“建筑抢修”等经典题的对比
做完 P3619，你一定会联想到另一道更出名的题：P4053 [JSOI2007] 建筑抢修。那道题也是任务调度，也是按某个规则排序，但它在排序之后还要用堆动态决定“哪些任务可以被完成”，而不是简单地线性扫描一遍。
区别在哪里？P3619 要求的是全部任务都必须完成，不做取舍，所以排序后线性判断即可。建筑抢修问的是最多能完成几个，允许放弃部分任务，所以排序后不能直接扫描，得用优先队列维护一个已选集合，遇到时间不够时，腾出空间留下收益更大的。
如果你能把 P3619 和建筑抢修放在一起对比，任务调度题的两种常见形态基本就掌握了一半。之后遇到类似的题，先判断它到底是“全做完”还是“尽量多做”，再决定用纯排序还是排序 + 堆。
5.3 关于 C++ 实现的一点额外建议
这道题代码很短，用什么编辑器都无所谓，VS Code 配好 C/C++ 环境就能跑。我自己的流程是：先在本地写好代码，造两组自测数据跑通，再用命令行编译一次，确认没有警告，最后提交到在线评测系统。
有些同学喜欢在 IDE 里直接点运行，但我建议至少学会g++ -std=c++17 magic.cpp -o magic这种命令行编译方式。原因很简单，评测环境就是命令行，提前熟悉编译体验可以避免不少提交时的低级问题。
还有一个习惯我觉得值得分享：这道题的代码保存成magic.cpp，文件名就用拼音或英文，不要乱七八糟加中文。等你刷的题多了，回看本地文件夹时，清晰的文件命名能帮你快速找到代码。这不是什么硬性要求，纯粹是实操后的个人建议。
最后再分享一个小技巧。做完这道题，建议立刻把排序规则里的不等式自己独立推一遍，然后不看题解把代码重写一遍。如果你能在十分钟内写出一个全部 AC 的版本，说明这套贪心你已经真正吃透了。这个题目本身不复杂，但它考察的“交换论证 + 分组排序”思路，在后面很多贪心题里都会反复出现。早一点把这个思维模型装进脑子，后面刷题会轻松很多。
