CSP-S 提高级 · CSP 2025 提高级第一轮 第 15 题

$5$ 个独立的、不可抢占的任务 $A_1, A_2, A_3, A_4, A_5$ 需要在一台机器上执行（从时间 $0$ 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 $3, 4, 2, 5, 1$ 和 $5, 10, 3, 15, 11$。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？

这题核心就是贪心策略的选择。拿到题别急着算，先想目标：要最小化超时惩罚，也就是尽量别让任务晚于截止时间。单机调度里，让任务按‘截止时间从早到晚’排（EDD 策略），是最稳妥的。只要按这个顺序跑一遍，就能立刻看出哪些会超时，哪些不会。

很多同学习惯看到‘优化’就下意识选‘最短处理时间优先（SPT）’，因为 SPT 在最小化平均完成时间或总周转时间时确实是最优的。但本题的惩罚规则很特殊：超时惩罚等于该任务的处理时长，本质上是想最小化‘最大延迟’或避免任何延迟。这时候 SPT 就会翻车——它只顾着把短任务先跑完，反而可能把截止时间早的长任务挤到后面去超时。另一个坑是以为‘任意顺序都行’，其实顺序不同，超时任务集合完全不同，总惩罚可能从 0 跳到 3 甚至更高。

考点定位：单机调度中的贪心策略选择（EDD vs SPT），以及超时惩罚的计算。

概念回顾：

• EDD（Earliest Due Date）：按截止时间从早到晚排序执行，经典结论是它能最小化最大延迟；若存在一种调度能让所有任务都按时完成，EDD 一定能找到它。
• SPT（Shortest Processing Time）：按处理时长从短到长排序，经典结论是它能最小化平均完成时间或总周转时间，但对延迟不敏感。

命题人视角： 这道题故意把惩罚设成‘超时则罚处理时长’，这样总惩罚 = 所有超时任务的处理时长之和。命题人想考的是：学生在面对‘避免超时’的目标时，会不会被‘最短处理时间优先’的惯性思维带偏。大多数同学会先算 SPT，然后发现 A₁ 超时，得出惩罚 3；再回头算 EDD，发现全部按时，惩罚 0，从而意识到策略选错了。

思考心法（拿到题怎么一步步推）： 1) 先看清目标：最小化总惩罚 = 最小化超时任务的处理时长和。 2) 联想经典：单机调度里，和‘延迟’相关的贪心通常是 EDD；和‘完成时间’相关的贪心通常是 SPT。 3) 尝试验证：按截止时间排序（EDD）跑一遍，记录每个任务的完成时刻，判断是否超时；再按处理时长排序（SPT）跑一遍，对比结果。 4) 得出结论：哪个策略得到的总惩罚更小，就选哪个。

具体计算（题目数据：p=[3,4,2,5,1]，d=[5,10,3,15,11]）：

• EDD 顺序：A₃(d=3), A₁(d=5), A₂(d=10), A₅(d=11), A₄(d=15)

完成时刻：2,5,9,10,15 → 全部 ≤ 各自截止时间，总惩罚 = 0。

• SPT 顺序：A₅(1), A₃(2), A₁(3), A₂(4), A₄(5)

完成时刻：1,3,6,10,15 → A₁ 完成于 6 > 5，超时，惩罚 = 3。 显然 EDD 更优。

避坑提醒：

• 别把 SPT 当成‘万能最优’，它只对平均完成时间或总周转时间最优。
• 别以为‘只要有一个任务超时，随便调序就能救’——顺序不同，超时集合完全不同。
• 别忽略题目给的惩罚规则，一旦规则变成‘超时罚处理时长’，目标就从‘最小化平均完成时间’变成了‘最小化最大延迟’，策略自然要换。

考频与趋势： 在贪心算法这一大类里，题库共考过 71 题，覆盖 9 个考试级别（2010-2026）。逐年分布：2010 年 1 题、2019 年 3 题、2020 年 3 题、2021 年 2 题、2022 年 1 题、2023 年 3 题、2024 年 16 题、2025 年 12 题、2026 年 24 题、null 年 6 题。分赛事来看，GESP 五级 25 题、六级 13 题、CSP 入门级 12 题、GESP 八级 8 题、GESP 七级 5 题、CSP 提高级 5 题、GESP 三级 1 题、GESP 四级 1 题、NOIP 普及组 初赛 1 题。 调度类贪心（EDD/SPT）在近年明显升温：2024 年 16 题、2025 年 12 题、2026 年 24 题，合计 52 题，占全年贪心题的大头。尤其是 CSP 提高级，这类题占比稳定在 5 题左右，说明命题人持续喜欢在‘策略选择’上挖坑。

预测： 基于上述数据，未来一年（2026 年）贪心算法仍将是高频考点，调度类题目大概率继续出现，且更可能以‘多种目标函数对比’的形式考察（例如同时问平均完成时间和最大延迟）。暂无足够依据预测具体年份或具体赛别的题目数量变化，但‘按截止时间排序’这一核心思想在单机调度中几乎不会过时。