洛谷P3619《魔法》题解:贪心排序与任务调度

发布时间:2026/11/19 11:26:12

洛谷P3619《魔法》题解:贪心排序与任务调度 聊一道洛谷的 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 的版本说明这套贪心你已经真正吃透了。这个题目本身不复杂但它考察的“交换论证 分组排序”思路在后面很多贪心题里都会反复出现。早一点把这个思维模型装进脑子后面刷题会轻松很多。
延伸阅读

更多相关文章

2026/11/19 3:46:26

Vidocoding 开发流程实战:用 AGENTS.md 与 PRD 打通技术设计到落地

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/16 16:07:53

深度学习视觉问答系统实战:从模型原理到毕业设计落地

简介:这是一份面向毕业设计场景的Python深度学习视觉问答系统完整项目,适合计算机、人工智能等专业学生用于毕设、期末大作业或课程设计。项目围绕图像问答任务,实现了从数据预处理、特征提取、模型构建到训练评估的完整流程,包含…

2026/11/16 18:12:46

人脸活体检测比赛Top方案复现:从ACER指标到时序建模全解析

CVPR2019那届ChaLearn人脸防伪挑战赛,应该是我入行以来复现过最“拧巴”的一场比赛模型。表面上比的是“能不能分清真人脸和假人脸”,实际上拼的是对成像物理过程的理解、对数据不均匀性的处理,以及对评估指标的理解深度。我当时花了两周时间…

2026/11/19 11:23:27

南昌市低压电工证五月考试安排内部消息来了,怕考不过白交培训费

南昌市低压电工证五月考试安排内部消息来了,怕考不过白交培训费 你是不是正盯着手机里那条“南昌市低压电工证五月考试安排”的信息,心里打鼓?怕考不过,培训费打了水漂,这种焦虑再正常不过。最近不少人在问,听说这次考试有“内部消息”流出?真的假的?…

2026/11/19 11:23:27

电工证都是电子证么吗值不值得考 工地太忙根本没时间复习考试

电工证都是电子证么吗值不值得考 工地太忙根本没时间复习考试 工地太忙根本没时间复习考试,这几乎是所有电工从业者的真实写照。特别是对于那些刚从其他岗位转岗过来的人来说,既要面对高强度的工作节奏,又要应对特种作业操作证考试,压力不言而喻。很多人…

2026/11/19 11:23:27

荔湾高压电工证流程报考条件与考试时间值不值得考

荔湾高压电工证流程报考条件与考试时间值不值得考 证书过期了不知道怎么复审延期?荔湾高压电工证流程不熟悉,很多人在遇到证书即将到期时才慌了神,甚至有人因为操作不当,导致证书失效,进而影响工作和收入。 荔湾高压电工证流程…

2026/11/19 11:23:27

工地太忙根本没时间复习考试?徐州哪考维修电工证的真实经历全揭秘

工地太忙根本没时间复习考试?徐州哪考维修电工证的真实经历全揭秘 工地太忙根本没时间复习考试,这话不是我说的,是干了三年电工的王师傅说的。他现在每天在徐州工地来回跑,手头活儿一多,连看手机的时间都没有,更别提抽空复习维修电工证的考试内容了。可…

2026/11/19 11:18:26

焊工证能代替电工证吗 郑州报考避坑指南

焊工证能代替电工证吗 郑州报考避坑指南 证书过期了不知道怎么复审延期,这事儿我见过太多了。上周,一个三门峡劳务班组的负责人老李找我,说他手下的电工证都快到期了,但公司催得紧,他想赶紧安排复审,结果发现有些证根本不能替代,比如焊工证和电工证是…

2026/11/18 21:12:58

电工证考试口诉怎么准备值不值得考

电工证考试口诉怎么准备值不值得考 实操考试心里没底怕挂科,这是大多数准备考电工证的人心里最真实的感受。尤其是面对【电工证考试口诉】环节,很多人不知道该怎么准备,甚至担心自己说不好就被淘汰。其实,只要掌握方法, 值不值得考…

2026/11/18 21:55:23

桑植县考电工证千万别踩坑!报名全流程教你避坑

桑植县考电工证千万别踩坑!报名全流程教你避坑 你是不是也遇到过这种情况:想考个电工证,但不知道从哪儿下手,怕被中介坑,怕花冤枉钱,更怕考了证还不能用?别急,这正是你该看这篇文章的原因。在桑植县考电工证,确实有很多人被坑过,但只要你知道流程、…

2026/11/19 0:04:42

深圳电工证培训考场模拟考试题库:郑州报考避坑指南

深圳电工证培训考场模拟考试题库:郑州报考避坑指南 证书过期了不知道怎么复审延期,很多人在遇到这个问题的时候才意识到特种作业证的重要性。其实,不管是电工证、焊工证还是高处作业证,这些证书不仅是上岗的“通行证”,更是法律对安全操作的硬性要求。尤…

2026/11/19 0:04:42

天津电工证查询入口多少钱能报上名

天津电工证查询入口多少钱能报上名 学历不高怕报不上名?别急,天津电工证查询入口其实没你想的那么难。今天咱们就来聊聊,怎么用最低的门槛、最少的钱,把电工证拿下来,还能查得到、用得上。 电工证到底值不值?先搞清楚它的作用…

2026/11/18 12:37:05

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

在智慧养宠时代,基于视觉的宠物身份识别技术正逐步从实验室走向家庭应用。然而,与配合度高的人类不同,宠物是典型的“非合作生物识别对象”——它们不会主动配合摄像头调整姿态,更无法控制光照环境。实际应用中,我们常…

2026/11/18 1:15:04

SSM电子书店源码全解析:结构、原理、部署与排错实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

还想了解更多?直接咨询顾问

免费诊断 + 免费方案 + 透明报价。

全国咨询热线400-8866-253
免费获取方案
☎咨询二维码 ☎ ↑