聊一道洛谷的 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 很小的时候这思路没问题比如 N5全排列才 120 种。但 N 稍大一点比如 N1515! 已经是 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先做 A3 够了做完剩 2再做 B 也够。如果先做 B3 也够但做完剩 0A 需要 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_jcur 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 用一个小例子感受排序差异我用一组简化数据来演示这个排序的重要性两个任务任务 At 2b -1任务 Bt 1b -2初始时间 cur 3。按 t b 降序排序A 的 t b 1B 的 t b -1所以先做 A。cur 2做 A剩余 2 单位再做 B2 1完成剩余 1。成功。如果按 t 升序排序就会先做 B。cur 1做 B剩余 1 单位再做 A1 2失败。这里就能看出排序规则选错答案直接从 Yes 变成 No。这组数据很小但它把“做完后还剩多少”的决定性作用表现得非常清楚。3. C实现与完整代码3.1 结构体定义与比较函数这道题核心代码非常简单一个结构体存 t 和 b 就够。排序的时候用自定义比较函数注意正收益和负收益要分别写两个比较规则。我习惯把cmpPos和cmpNeg分开写这样逻辑清晰后面排错也方便。有同学喜欢用一个比较函数配合标志位处理也可以但我觉得分开写更直白。比较函数要注意返回值的含义true表示第一个参数应该排在第二个参数前面。正收益组就是a.t b.t负收益组就是a.t a.b b.t b.b注意是大于号别写成小于号。结构体本身不需要重载运算符两行代码就够用。有些题解会给结构体写构造函数但这里完全没必要C11 之后直接用花括号初始化{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; vectorTask 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; }这段代码在洛谷上可以直接跑编译选项用默认的 C17 就行。头文件直接写万能头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 -stdc17 magic.cpp -o magic这种命令行编译方式。原因很简单评测环境就是命令行提前熟悉编译体验可以避免不少提交时的低级问题。还有一个习惯我觉得值得分享这道题的代码保存成magic.cpp文件名就用拼音或英文不要乱七八糟加中文。等你刷的题多了回看本地文件夹时清晰的文件命名能帮你快速找到代码。这不是什么硬性要求纯粹是实操后的个人建议。最后再分享一个小技巧。做完这道题建议立刻把排序规则里的不等式自己独立推一遍然后不看题解把代码重写一遍。如果你能在十分钟内写出一个全部 AC 的版本说明这套贪心你已经真正吃透了。这个题目本身不复杂但它考察的“交换论证 分组排序”思路在后面很多贪心题里都会反复出现。早一点把这个思维模型装进脑子后面刷题会轻松很多。