★ FEATURED ARTICLE 打卡信奥刷题到 P3619 这道题时我一度以为它只是普通的模拟题结果连续提交两次都栽在同一个地方。这道名为《魔法》的 C 信奥题表面上是让你处理一堆来源不明的咒语剥掉那层魔法外衣之后其实是典型的“门槛 收益”任务调度模型。它很适合正在准备 CSP-J/S、NOIP 或者刷洛谷题单的同学拿来练贪心排序因为题目本身不涉及高深数据结构真正的考点全藏在“按什么顺序处理任务”这一步里。这篇文章我会把 P3619 从拆题、推导排序规则、C 实现到边界测试完整讲一遍重点解释为什么负收益任务要按a b降序处理而不是按门槛或者按掉血量排序。后面还会附上我调试时踩过的两个真实反例以及这类“能量管理”题目的通用解法框架。1. 拆解 P3619魔法题面下的任务调度模型1.1 题目到底让你干什么P3619 的题面包装得很花哨说你是魔法学徒拥有初始魔力值 w面前有一堆魔法卷轴。每个卷轴有两个整数属性研读它所需的当前魔力下限 a以及研读完成后魔力值的变化量 b。b 可以是正数也可以是负数甚至可能是 0。题目问的是是否存在一种研读顺序让你能把所有卷轴全部读完。把“魔法卷轴”“魔力值”这些词全部换成“任务”和“体力值”你会发现这就是一个非常经典的任务调度判定问题每个任务有一个最低完成门槛 a每个任务完成后你的资源会变化 b增加或减少初始资源为 w要求资源全程不能低于当前任务的门槛问能否按某种顺序做完所有任务。这种模型在算法竞赛里出现频率极高常见的变体有“打怪升级”“闯关拿宝石”“做任务攒体力”等等。P3619 的难点不在于读题而在于一旦你开始思考“先做哪个任务”就很容易掉进排序的陷阱里。1.2 为什么第一眼会想到贪心却容易排序排错面对这种题第一反应往往是贪心n 个任务每个任务都有门槛和收益那肯定要先做“性价比高”的任务。但“性价比高”这四个字很模糊不同的人会产生不同的直觉。我的第一个想法是按 b 降序先把收益最高的做了让魔力值快速增长第二个想法是按 a 升序先做门槛最低的毕竟门槛低的更容易完成。这两个直觉都存在严重问题。按收益降序你可能会先去做一个门槛极高、当前根本完成不了的任务按门槛升序你可能会因为某个任务掉血太多导致后面门槛稍高的任务反而完成不了。问题根源在于任务之间不是独立的做完一个任务后魔力值会变化它会把后续任务的可完成性彻底改变。正确的思考方式是先把任务拆成两类b 0 的正收益任务和 b 0 的负收益任务。正收益任务只会让魔力值变大做完之后对后续任务只有帮助、没有副作用所以应该优先处理。负收益任务会消耗魔力值需要单独设计排序规则。两条线分别排好序再拼起来模拟一遍这就是这道题的完整解法。2. 排序规则的证明为什么负收益任务按 a b 降序2.1 正收益任务先做门槛升序的交换论证先把正收益任务看成一个整体。任何包含负收益任务的顺序里如果把一个正收益任务 X 移动到某个负收益任务 Y 的前面情况只会变得更好还是可能变差答案是只会更好。理由很简单先做 X魔力值会加上一个正数之后再做 Y 时门槛更容易满足如果先做 Y魔力值已经被压低了再去做 X 时门槛满足难度不变或者更大。所以所有正收益任务都应该排在所有负收益任务之前。那么正收益任务内部怎么排序假设有两个正收益任务 X(a1, b1)、Y(a2, b2)其中 b1 0、b2 0并且 a1 a2。如果存在一种最优顺序是先 Y 后 X我们尝试把它交换成先 X 后 Y。先 Y 后 X 可行意味着当前魔力值 w 满足 w a2并且做完 Y 后还满足 w b2 a1。现在考虑先 X 后 Y因为 a1 a2且 w a2所以 w a1 成立第一个任务 X 可以开始。再因为 b1 0有 w b1 w a2所以做完 X 之后魔力值一定不低于 a2Y 也能开始。两个任务都能按新顺序完成。这说明正收益任务按照门槛 a 升序处理一定不劣于任何其他顺序。这也是最符合直觉的门槛低的正收益任务先拿掉魔力值越滚越大后面门槛高的任务自然就能完成了。如果连门槛最低的正收益任务都完成不了那剩下的正收益任务门槛只会更高更不可能完成可以直接判定失败。2.2 负收益任务排序一个反例逼出结论负收益任务才是 P3619 真正的坑。先来看一个反例它否定了“按门槛升序”的直觉。假设当前魔力值 w 4有两个任务任务 Aa 2b -2也就是要求魔力至少 2完成后减少 2任务 Ba 3b -1也就是要求魔力至少 3完成后减少 1。如果按门槛 a 升序会先做 A 再做 B。过程是当前魔力 4满足 A 的门槛 2做完后魔力变成 2接着做 B需要魔力至少 3但当前只有 2失败。可实际上这道题是有解的先做 B。当前魔力 4满足 B 的门槛 3做完后魔力变成 3再去做 A3 满足门槛 2做完后魔力变成 1成功。这个反例说明负收益任务不能只看门槛。A 的门槛低但它掉血多做完只剩 2B 的门槛高但它掉血少做完还剩 3。先做完 B 之后中间状态的魔力值更高给后面的任务留了更多余量。这引出了正确的直觉两个负收益任务无论先做哪个最终魔力值都一样都是 w b1 b2区别在于第一个任务做完后、第二个任务门槛判定前的那个中间状态。为了不让中间状态成为瓶颈应该优先做“完成后剩余魔力更高”的任务。这个关键值就是 a b因为做完后魔力等于当前魔力 w 加 b而 b (a b) - a也就是做完后相对门槛后还有多少余量。所以负收益任务内部要按 a b 从大到小排序。2.3 用数学把“中间状态安全”讲清楚上面是直观理解还可以用交换论证严格证明。设当前魔力值足够同时开始两个负收益任务 X(a1, b1)、Y(a2, b2)其中 b1、b2 都小于等于 0。先做 X 再做 Y 可行需要同时满足w a1w b1 a2等价于 w a2 - b1先做 Y 再做 X 可行需要同时满足w a2w b2 a1等价于 w a1 - b2我们希望找到一个与 w 无关的排序规则。假设先 X 后 Y 优于先 Y 后 X也就是说当后一种顺序可行时前一种顺序一定也可行。这意味着前一种顺序对 w 的下界要求不能更高即max(a1, a2 - b1) max(a2, a1 - b2)对这个不等式做变形可以推出它等价于 a1 b1 a2 b2。也就是说当任务 X 的 a b 值大于等于任务 Y 的 a b 值时先做 X 不劣。所以负收益任务按 a b 降序排序是正确且必要的。个人建议在刷题的时候把上面这段推导完整写一遍。因为只看结论很容易记混甚至有人会错记成“按 b 从大到小”或者“按 a 从大到小”。只要自己动手推一次就会明白为什么排序关键字是 a b而不是别的。3. C 代码实现与逐段解读3.1 数据结构与读入既然要把任务分成正负两组我直接用结构体存每个任务并用两个 vector 分别存放 b 0 和 b 0 的任务。a 和 b 用 long long 存因为后续累加魔力值时n 个任务的收益叠加起来可能会超过 int 范围这是信奥赛场常见的数据类型坑。#include bits/stdc.h using namespace std; struct Task { long long need; // 研读所需的当前魔力下限 a long long delta; // 完成后魔力变化 b }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; long long w; cin n w; vectorTask earn; // delta 0 vectorTask cost; // delta 0 for (int i 0; i n; i) { long long a, b; cin a b; if (b 0) earn.push_back({a, b}); else cost.push_back({a, b}); } // 排序和模拟见下文 } return 0; }这里有个细节值得说明为什么把 b 0 的任务放进 cost 组而不是 earn 组因为 b 0 的任务不会让魔力值增加把它放在正收益任务之后处理符合“正收益全部先做”的大原则。它在 cost 组内按 a b 排序由于 b 是 0其实等价于按 a 降序这也能保证模拟时不会因为顺序问题出错。如果你把它放进 earn 组按 a 升序排序也一样没问题但要注意不要让它出现在两个组里否则会重复模拟。3.2 排序代码lambda 表达式写法分组完成之后分别对两个组排序。earn 组按 need 升序cost 组按 need delta 降序。sort(earn.begin(), earn.end(), [](const Task x, const Task y) { return x.need y.need; }); sort(cost.begin(), cost.end(), [](const Task x, const Task y) { return x.need x.delta y.need y.delta; });这里 sort 的第三个参数是 lambda 表达式属于 C11 之后的标准写法。信奥竞赛中这种写法非常常见比手写 cmp 函数更简洁。cost 组的比较器直接对两个 long long 做加法一般情况下没有溢出风险因为 a 和 b 通常都是 int 量级就算极端一些long long 也能扛住。不过如果题目数据范围特别大可以在读取时就把 a b 预先存成另一个字段避免重复计算。3.3 模拟判定循环与结果输出排序完成后按顺序模拟一遍。先做 earn 组再做 cost 组。任意一次判定失败就说明不存在合法顺序输出 NO全部通过则输出 YES。bool ok true; for (const auto task : earn) { if (w task.need) { ok false; break; } w task.delta; } if (ok) { for (const auto task : cost) { if (w task.need) { ok false; break; } w task.delta; } } cout (ok ? YES : NO) \n;这段模拟逻辑有一个隐蔽的优点当 earn 组中某个任务失败时直接 break 是安全的不需要尝试跳过它去做后面的任务。因为 earn 组已经按门槛升序排好了当前任务失败意味着当前魔力值低于它的门槛而后面任务的门槛只会更高收益再大也弥补不了“门槛本身就够不到”的事实。这样代码既简洁又不容易出错。4. 评测中的边界情况与调试经验4.1 数据类型、输入加速与多组数据P3619 的评测圈数 T 可能比较大每组数据也有一定规模所以输入加速是必要的。我在代码里写了ios::sync_with_stdio(false);和cin.tie(nullptr);这两行能明显减少 cin 的 IO 开销。如果你用 scanf那就不需要这两行但混用 cin 和 scanf 一定要避免。数据类型的坑容易被忽略。a 和 b 看起来像 int但初始魔力 w 经过 n 次正收益累加后可能涨到很大经过 n 次负收益消耗后也可能变成很大的负数。用 int 存一旦溢出比较结果就会错得莫名其妙。所以我在结构体里直接用了 long long排序和累加也都是 long long这一手能在评测时省下很多排查时间。多组测试数据也是一个经典雷区。vector 在每次 while 循环里重新创建不会保留上一组的数据这是比较稳妥的写法。千万不要把 vector 定义在循环外面然后忘记 clear否则上一组残留的任务会混进下一组导致结果错乱。4.2 边界测试数据设计我调试这道题时设计了一批边界数据这里直接分享出来你可以拿它们验证自己的代码场景输入期望输出说明单任务恰好满足门槛1 3 / 3 1YES比较要用不是初始魔力不足1 2 / 3 1NO门槛比初始魔力大必然失败负收益排序反例1 4 / 2 -2 / 3 -1YES按 ab 降序应先做 3,-1正收益必须优先1 1 / 1 10 / 5 -3YES先做负收益会直接失败全负收益无法完成1 2 / 3 -1 / 3 -1NO初始魔力不足无解其中“负收益排序反例”最能检验排序规则是否正确。如果代码里用的是按 a 升序或者按 b 降序这组数据就会输出 NO而正确答案是 YES。另外要注意边界判断用的是而不是当魔力值恰好等于任务门槛时是可以执行的写错这个符号会导致边界数据 WA。4.3 我在 OJ 上 WA 过的两个真实场景第一次 WA 是栽在负收益任务的排序关键字上。我最初写的是按 b 从大到小排理由很朴素掉血少的先做掉血多的后做。结果遇到上面那组反例直接挂掉。后来我手动模拟了一遍才发现掉血少不代表完成后剩余魔力多关键要看 a b也就是“做完后还剩下多少”。从那以后我再看到掉血任务第一反应就是先算结束剩余值。第二次 WA 更隐蔽是因为我把 b 0 的任务单独开了一个 vector然后只模拟了 earn 和 cost 两个组第三组被遗漏了。b 0 的任务虽然不会改变魔力值但它的门槛是真实存在的必须参与模拟。如果当时不想清楚这一点代码结构很容易写成分组时把 b 0 漏掉或者在排序上出现逻辑混乱。现在我的习惯是凡是 b 0 就统一放进 cost 组让排序和模拟逻辑保持一致。5. 从 P3619 延伸一类“能量任务”题的通解框架5.1 三步走分组、排序、模拟做完 P3619 之后我发现它代表了一整类题目给你一个初始能量值再给你若干任务每个任务有门槛和能量变化判断能否全部完成或求某种最优结果。这类题只要认准三个步骤基本不会跑偏。第一步是分组。把正收益任务和负收益任务分开。正收益任务只会增强你的状态负收益任务会削弱你的状态。分开之后处理顺序的大框架就定了先增强后削弱。第二步是排序。正收益任务按门槛 a 升序负收益任务按 a b 降序。前者保证用最低的门槛滚雪球后者保证中间状态尽量高。这两个排序规则建议直接当模板记住同时理解背后的证明免得在变式题里用错。第三步是模拟。严格按照排序后的顺序逐个判定、逐个更新能量值。模拟过程中只要有一次w need就判定失败。最后如果题目还要求最终能量大于某个值就额外加一个最终判断。5.2 变式如果任务是可选做或可不做的P3619 要求做完所有任务但很多题目会改成“可以选择部分任务做求最多能做多少个”。这种变式在分组后思路依然清晰正收益任务只要能做就做按门槛升序扫描一遍统计个数负收益任务则不能简单全做需要结合剩余能量做进一步决策。对于负收益任务的最多完成数量一个可行策略是仍然按 a b 降序排序然后依次判断能否完成能完成就计入答案并更新能量不能完成就跳过。你可能会担心贪心是否成立但实际上这类任务如果再加上一些限制条件往往会变成背包 DP 或状态压缩 DP单纯贪心就不一定对了。我的建议是遇到这种变式先判断题目数据范围如果 n 比较大、能量值也比较大通常意味着贪心可行如果 n 很小比如不超过 20那很可能是状压 DP 或二分答案。另一种高频变式是“求最小初始能量 w”。解法是二分答案。将 w 作为二分对象每次用一个 check 函数判断当前 w 能否完成全部任务。check 函数内部就是 P3619 的分组、排序、模拟三步走。这样 P3619 的代码可以直接复用二分把答案空间从模拟问题转换成判定问题复杂度从 O(n) 变成 O(n log w)在数据范围内完全可行。5.3 给刷题打卡的学弟学妹的一点建议我自己的刷题习惯是打卡一道题之后不急着下一道而是花点时间把这道题归类进自己的“模型库”。P3619 我就归进了“能量管理”这一类和它同类的还有不少贪心题。归类的意义在于下次再见到类似模型可以快速识别出分组、排序、模拟这套流程而不是每次从零开始猜。对于这道题我还建议你把排序证明写在代码注释里或者写成题解笔记。因为只记结论的话过两个星期很可能就忘了 a b 降序这个关键字然后重新踩进门槛排序的坑。写一遍推导过程相当于把结论嵌进长期记忆里比反复刷同类题更有效。最后提醒一句如果你在 OJ 上做了很久还 WA先别急着怀疑数据有问题回头检查一下 b 0 的分组、比较符号是还是、有没有多组数据残留这三个位置。这三个坑我全都踩过一遍它们几乎覆盖了 P3619 除了排序之外的绝大多数丢分点。
阅读完成 · 觉得有帮助？
