企业官网建设流程全解析

打卡信奥刷题到 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 之后魔力值一定不低于 a2，Y 也能开始。两个任务都能按新顺序完成。

这说明，正收益任务按照门槛 a 升序处理，一定不劣于任何其他顺序。这也是最符合直觉的：门槛低的正收益任务先拿掉，魔力值越滚越大，后面门槛高的任务自然就能完成了。如果连门槛最低的正收益任务都完成不了，那剩下的正收益任务门槛只会更高，更不可能完成，可以直接判定失败。

2.2 负收益任务排序：一个反例逼出结论

负收益任务才是 P3619 真正的坑。先来看一个反例，它否定了“按门槛升序”的直觉。

假设当前魔力值 w = 4，有两个任务：

• 任务 A：a = 2，b = -2，也就是要求魔力至少 2，完成后减少 2；
• 任务 B：a = 3，b = -1，也就是要求魔力至少 3，完成后减少 1。

如果按门槛 a 升序，会先做 A 再做 B。过程是：当前魔力 4，满足 A 的门槛 2，做完后魔力变成 2；接着做 B，需要魔力至少 3，但当前只有 2，失败。

可实际上这道题是有解的：先做 B。当前魔力 4，满足 B 的门槛 3，做完后魔力变成 3；再去做 A，3 满足门槛 2，做完后魔力变成 1，成功。

这个反例说明，负收益任务不能只看门槛。A 的门槛低，但它掉血多，做完只剩 2；B 的门槛高，但它掉血少，做完还剩 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 >= a1
• w + b1 >= a2，等价于 w >= a2 - b1

先做 Y 再做 X 可行，需要同时满足：

• w >= a2
• w + 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; vector<Task> earn; // delta > 0 vector<Task> 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 表达式，属于 C++11 之后的标准写法。信奥竞赛中这种写法非常常见，比手写 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 边界测试数据设计

我调试这道题时设计了一批边界数据，这里直接分享出来，你可以拿它们验证自己的代码：

其中“负收益排序反例”最能检验排序规则是否正确。如果代码里用的是按 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 除了排序之外的绝大多数丢分点。