01 / 本课学习路线
本课学习路线
阅读与推演约 110 分钟，练习约 60 分钟，进阶练习另需约 20 分钟
02 / 学习目标与先修自测
学完本课你能做什么，以及开始前需要会什么
上一课的贪心「选定就不改」；本课多一个动作：接下之后发现超期，把已接的里面代价最大的撤掉。堆负责随时找到「代价最大的那个」。
| 学完后能做的事 | 正文位置 | 检查方式 |
|---|---|---|
| 口述带撤销的贪心的循环：接下、检查是否超期、撤销代价最大的 | 第 04 节 | 自查第 3 条、练习 4 |
| 用交换论证解释为什么撤销「耗时最大」 | 第 04 节末尾 | 自查第 4 条 |
| 说出 P3130 与 AI021 的两处不同（撤销的键、时间上限 T） | 第 05 节 | 自查第 2 条、练习 5 |
| 知道 heapq 是小顶堆，大顶堆用存负数实现 | 第 03 节 | 自查第 5 条 |
| 独立通过 AI021、P3130 | 第 07 节 | 必做任务 1、2 |
先修自测：下面 5 题请先自己写答案，再展开对照。答不出的按括号里的位置补看再回来。本课假定你已完成模块 2 的「堆与 Top-K 问题」和上一课「贪心算法与交换论证」。
| 题号 | 题目 | 补看位置 |
|---|---|---|
| 自测 1 | h = []，依次 heapq.heappush(h, 3)、heappush(h, 1)、heappush(h, 2) 后 heapq.heappop(h) 返回什么？ | 堆与 Top-K 问题第 03 节 |
| 自测 2 | 要让 heappop 先弹出最大的数，入堆时存什么？弹出后怎么还原？ | 堆与 Top-K 问题第 04 节 |
| 自测 3 | sorted([(3, 5), (2, 2), (2, 4)], key=lambda x: x[1]) 得到什么？ | 排序与并列规则 |
| 自测 4 | 堆里每个元素代表「一个已接下的任务」，len(heap) 代表什么？ | 列表 |
| 自测 5 | min(k, T)：k = 5、T = 2 时是多少？它在本课里用来做什么？ | 常用内置函数 |
展开先修自测答案
自测 1：1——heapq 是小顶堆，弹出的永远是最小值。
自测 2：存负数（heappush(h, -t)）；弹出的是 -t_max，used += heappop(h) 就等于减去 t_max。
自测 3：[(2, 2), (2, 4), (3, 5)]——按每个元组的第 2 项（截止时刻）升序，这就是 AI021 的排序键。
自测 4：已接下（且尚未撤销）的任务数——AI021 的答案就是最后的 len(heap)。
自测 5：2。P3130 里最晚处理时间不能超过总时间 T：一个任务最晚也只能在时刻 T 完成。
03 / 概念与术语
截止时刻、先接下、撤销、大顶堆与小顶堆
「带撤销的贪心」也叫反悔贪心：先按排序键接下，发现违反约束时撤销已接的里面最不划算的那个。
| 术语 | 含义 | 代码里的位置 |
|---|---|---|
| 截止时刻 d | 任务必须在 d 之前（含 d）完成 | 排序键 tasks.sort()（按 d） |
| 先接下 | 遇到一个任务就先放进已接集合，不先判断放不放得下 | heappush + used += t |
| 超期 | 已接任务的总耗时 > 当前任务的截止时刻 | if used > d |
| 撤销 | 从已接集合里拿掉代价最大的一个（AI021：耗时最大；P3130：报酬最小） | heappop |
| 大顶堆 / 小顶堆 | heapq 只有小顶堆；要「最大的在顶」就存负数 | heappush(heap, -t) |
| 已用时间 used | 已接任务的耗时之和；P3130 每个任务耗时 1，len(heap) 就是它 | used / len(heap) |
补充学习（选学）另一种写法：按时刻从后往前推进约 5 分钟P3130 题目页参考题解的思路，与本课写法等价
P3130 还可以反过来按时刻推进：从时刻 T 到 1，每到一个时刻把「最晚处理时间等于它」的任务加入候选，从候选里取报酬最大的一个做。题目页参考题解就是这样写的（候选用排序，数据小可以通过；用堆则每步 O(log n)）。它和本课「先接下、超期撤销最小」得到同一个答案：两者都在保证「每个时刻至多做一个」的前提下留下报酬最大的集合。按时刻推进的写法要注意堆里可能残留已过期的候选——本题按时刻倒序加入所以不会过期；正序推进的题（例如按到达时间选任务）需要弹出时检查、过期就丢弃（惰性删除）。
04 / AI021 带撤销的贪心
接下、超期、撤销耗时最大的：两组示例与一组「撤销才能多完成」
AI021「GPU 训练任务调度」：第一行 n（≤ 10⁵），随后 n 行「耗时 t 截止 d」；从时刻 0 串行执行、不并行、不中断，输出最多能按期完成几个。题面示例 1：3 / 2 2 / 3 5 / 2 4 → 2；示例 2：2 / 5 3 / 4 2 → 0。
| 任务 | 接下后 used | 与截止比较 | 动作 | 堆（耗时） |
|---|---|---|---|---|
| (2, 2) | 2 | 2 ≤ 2 | 接 | {2} |
| (2, 4) | 4 | 4 ≤ 4 | 接 | {2, 2} |
| (3, 5) | 7 | 7 > 5 | 撤销耗时最大的 3，used 回到 4 | {2, 2} |
输出 2。示例 2：(4, 2) 接下 used 4 > 2 → 立即撤销自己；(5, 3) 同样 → 堆空，输出 0。「先接下再撤销自己」和「不接」结果相同，但代码只需要一条规则。
| 任务 | 接下后 used | 与截止比较 | 动作 | 堆 |
|---|---|---|---|---|
| (6, 6) | 6 | 6 ≤ 6 | 接 | {6} |
| (1, 7) | 7 | 7 ≤ 7 | 接 | {1, 6} |
| (1, 7) | 8 | 8 > 7 | 撤销 6，used = 2 | {1, 1} |
| (1, 7) | 3 | 3 ≤ 7 | 接 | {1, 1, 1} |
| (1, 7) | 4 | 4 ≤ 7 | 接 | {1, 1, 1, 1} |
输出 4。只跳过不撤销（放不下就不接）会停在 2：那个耗时 6 的任务占住了后面三个 1 的时间。撤销它，完成数先减 1 再加 3。
为什么撤销「耗时最大」：交换论证
超期时必须从已接集合里去掉一个，去掉哪个完成数都少 1；去掉耗时最大的，剩下集合的总耗时最小，之后每个任务面对的 used 都最小、最容易按期。假设最优方案此时去掉的不是耗时最大的那个 M 而是别的 X：把 X 留下、改去掉 M，总耗时只减不增，之后所有判断都不会变差——所以「撤销耗时最大」不比任何方案差。判断用 >：used 恰好等于截止时刻算按期（题面「含时刻 d」），1 / 5 5 应输出 1。
05 / P3130 报酬变体
堆里改存报酬，超期撤销报酬最小的；最晚时间与 T 取较小值
P3130「在规定时间内获得的最大报酬」：第一行总时间 T 与任务数 N（都 < 100），随后 N 行「最晚处理时间 k 报酬 l」；每个任务耗时 1、同一时间只做一个，在最晚时间之前完成才有报酬；输出最多报酬。题面没有给示例，下面的数字是本课自己算的：T = 3，(1,5)(1,3)(2,4)(3,2) → 11。
| 任务 | 接下后已接数 | 与最晚时间比较 | 动作 | 堆（报酬） |
|---|---|---|---|---|
| (1, 3) | 1 | 1 ≤ 1 | 接 | {3} |
| (1, 5) | 2 | 2 > 1 | 撤销报酬最小的 3 | {5} |
| (2, 4) | 2 | 2 ≤ 2 | 接 | {4, 5} |
| (3, 2) | 3 | 3 ≤ 3 | 接 | {2, 4, 5} |
输出 5 + 4 + 2 = 11。与 AI021 的两处不同：撤销的是报酬最小（小顶堆，不存负数）；最晚时间先与 T 取较小值——T = 2 时 (3, 2) 的最晚时间变成 2，第三个任务接下后 3 > 2，撤销报酬最小的 2，输出 9。
漏掉 min(k, T) 会怎样：2 3 / 5 10 / 5 9 / 5 8
正确：三个任务最晚时间都变成 2，只能做两个 → 撤销 8，输出 19 漏掉 min：最晚时间当成 5，三个都「按期」→ 输出 27，超过了总时间 2 能做的数量
06 / P2583 池化资源共享
按题目规则模拟：申请选「剩余不小于且最接近，并列编号最小」，释放归还那次申请
P2583「池化资源共享」（进阶）：第一行设备数 n 和操作数 m，第二行 n 台设备的初始剩余空间，随后 m 行操作：1 x 申请 x 的空间——在剩余空间 ≥ x 的设备里选剩余最接近 x 的（并列取编号最小），成功输出设备编号并扣减，失败输出 0；2 y 释放第 y 次申请——那次申请成功且未释放过时把空间还回原设备。题目页的示例以题目页为准；下面是本课自拟的一组教学用例，规则与题目页参考题解一致。
| 操作 | 候选设备（剩余 ≥ x） | 选择 | 输出 | 操作后剩余 |
|---|---|---|---|---|
| 1 4 | 1(5)、2(8)、3(6) | 最接近 4 的是 5 → 设备 1 | 1 | 1 8 6 |
| 1 5 | 2(8)、3(6) | 最接近 5 的是 6 → 设备 3 | 3 | 1 8 1 |
| 2 1 | — | 第 1 次申请（4，设备 1）归还 | （不输出） | 5 8 1 |
| 1 9 | 无 | 失败 | 0 | 5 8 1 |
| 1 5 | 1(5)、2(8) | 最接近 5 的是 5 → 设备 1 | 1 | 0 8 1 |
输出 1 3 0 1。「最接近」用严格小于比较更新，并列时保留先遇到的（编号更小的）；释放后要把那次申请标记为已释放，再次释放同一次不能重复归还。
07 / 从循环到程序
三道题的完整参考程序，每一步落在哪几行
先自己写完并提交一次，再展开对照。
| 步骤 | AI021 | P3130 | P2583 |
|---|---|---|---|
| 排序键 | 截止时刻 (d, t) 升序 | min(k, T) 升序 | 不排序：按操作顺序模拟 |
| 接下 | heappush(heap, -t)、used += t | heappush(heap, reward) | 扣减所选设备 |
| 超期判断 | used > d | len(heap) > deadline | — |
| 撤销 | used += heappop(heap)（弹出 -t_max） | heappop(heap)（弹出最小报酬） | 释放：归还并标记 |
| 答案 | len(heap) | sum(heap) | 逐次输出，空格分隔 |
带撤销的主循环（AI021 版）
Pythonimport sys, heapq
def main() -> None:
data = sys.stdin.read().split()
# tasks = [(t, d), ...] 耗时与截止时刻
tasks.sort(key=lambda x: x[1]) # 按截止时刻推进
heap: list[int] = [] # AI021：已接任务的耗时，大顶堆（heapq 是小顶堆，存负数实现）
used = 0
for t, d in tasks:
# 待完成 1：先接下当前任务（耗时入堆，并累加到已用时间 used）
# 待完成 2：used > d 时撤销耗时最大的任务，并从 used 中减去该任务耗时
...
print(len(heap))
main()heapq 只有小顶堆：AI021 要弹出「耗时最大」，入堆存负数。排序 O(n log n) + 每任务至多一次入堆一次出堆 O(log n)，n = 10⁵ 在时限内。
展开完整参考程序 1：AI021 GPU 训练任务调度（先自己写完并提交一次，再展开对照）
完整程序：AI021（标准输入 → 标准输出）
Pythonimport sys
import heapq
data = sys.stdin.read().split()
n = int(data[0])
tasks = []
for i in range(n):
t, d = int(data[1 + 2 * i]), int(data[2 + 2 * i])
tasks.append((d, t)) # (截止, 耗时)
tasks.sort() # 排序键：截止时刻
heap = [] # 已接任务的耗时；heapq 是小顶堆，存负数得到「最大的在顶」
used = 0 # 已接任务的总耗时
for d, t in tasks:
heapq.heappush(heap, -t) # 先接下
used += t
if used > d: # 超期：撤销已接任务里耗时最大的一个
used += heapq.heappop(heap) # 弹出的是 -t_max，加上它等于减去 t_max
print(len(heap)) # 堆里剩下的就是按期完成的任务用两组题面示例（2、0）、第 04 节的「一个 6 换四个 1」（4）和 1 / 5 5（1）核对；n = 10⁵ 时排序 + 堆在时限内。
展开完整参考程序 2：P3130 在规定时间内获得的最大报酬
完整程序：P3130（标准输入 → 标准输出）
Pythonimport sys
import heapq
data = sys.stdin.read().split()
T, n = int(data[0]), int(data[1])
tasks = []
for i in range(n):
k, l = int(data[2 + 2 * i]), int(data[3 + 2 * i])
tasks.append((min(k, T), l)) # 最晚处理时间不能超过总时间 T
tasks.sort() # 排序键：最晚处理时间
heap = [] # 已接任务的报酬；小顶堆，顶上是报酬最小的
for deadline, reward in tasks:
heapq.heappush(heap, reward) # 先接下（每个任务耗时 1，已接数量就是已用时间）
if len(heap) > deadline: # 超期：撤销报酬最小的
heapq.heappop(heap)
print(sum(heap))用第 05 节的 T = 3 → 11、T = 2 → 9 和「漏掉 min(k, T)」的 2 3 / 5 10 / 5 9 / 5 8 → 19 核对；题目页参考题解按时刻倒序取最大报酬，结果相同。
展开完整参考程序 3：P2583 池化资源共享（进阶练习）
完整程序：P2583（标准输入 → 标准输出）
Pythonimport sys
data = sys.stdin.read().split("\n")
n, m = map(int, data[0].split())
free = [int(x) for x in data[1].split()] # 每台设备的剩余空间，下标 0..n-1 对应设备号 1..n
requests = [] # 第 i 次申请：(申请量, 设备下标)，失败记 (-1, -1)
out = []
for line in data[2:2 + m]:
op, v = map(int, line.split())
if op == 1: # 申请 v 的空间：剩余 ≥ v 且剩余最接近 v 的设备，并列取编号最小
best = -1
for i in range(n):
if free[i] >= v and (best == -1 or free[i] < free[best]): # 严格小于：并列时保留更小的编号
best = i
if best == -1:
requests.append((-1, -1))
out.append(0)
else:
requests.append((v, best))
free[best] -= v
out.append(best + 1)
else: # 释放第 v 次申请
size, idx = requests[v - 1]
if idx != -1: # 只有成功且尚未释放的申请才归还
free[idx] += size
requests[v - 1] = (-1, -1)
print(" ".join(map(str, out)))用第 06 节的五条操作 → 1 3 0 1 核对。设备数不大，每次申请线性扫一遍即可。
08 / 边界、反例与复杂度
错误做法在具体输入上各输出什么
下面每一行都是一个具体的错误程序，给出输入、错误输出与正确输出；把参考程序改成对应写法就能复现。
| 错误做法 | 输入 | 错误输出 | 正确输出 | 判题结果 |
|---|---|---|---|---|
| AI021 只跳过不撤销（放不下就不接） | 5 / 6 6 / 1 7 ×4 | 2 | 4 | 答案错误（WA） |
| AI021 按耗时排序 | 6 / 10 10 / 10 12 / 1 13 / 1 14 / 1 15 / 1 16 | 4 | 5 | 答案错误（WA） |
| AI021 撤销耗时最小的（存正数） | 5 / 6 6 / 1 7 ×4 | 2 | 4 | 答案错误（WA） |
AI021 超期判断写 >= | 1 / 5 5 | 0 | 1 | 答案错误（WA） |
| P3130 漏掉 min(k, T) | 2 3 / 5 10 / 5 9 / 5 8 | 27 | 19 | 答案错误（WA） |
| P3130 撤销报酬最大的 | 第 05 节四任务，T = 3 | 9 | 11 | 答案错误（WA） |
P2583 并列取编号大（比较写 <=） | 2 1 / 4 4 / 1 3 | 2 | 1 | 答案错误（WA） |
| P2583 同一次申请释放两次都归还 | 1 4 / 5 / 1 3 / 2 1 / 2 1 / 1 8 | 1 1 | 1 0 | 答案错误（WA） |
第三行：撤销耗时最小的会把刚接下的 1 撤掉、留下 6，后面的 1 都放不下。
| 做法 | 时间 | 本课规模下 |
|---|---|---|
| 排序 + 堆 | O(n log n) | AI021 n = 10⁵ 可通过 |
| 每次线性扫已接集合找最大 | O(n²) | n = 10⁵ 约 10¹⁰，超时 |
| P2583 每次申请扫全部设备 | O(m·n) | 设备数与操作数都小，可通过 |
09 / 渐进练习与参考答案
跟做 → 改一个条件 → 独立实现 → 迁移
每题先在纸上或文件里做完，再展开答案。
练习 1（跟做）：按第 04 节表的格式逐任务推演 6 / 10 10 / 10 12 / 1 13 / 1 14 / 1 15 / 1 16，写出每一步的 used 和堆。
展开练习 1 答案
(10,10) 接，used 10；(10,12) 接后 20 > 12，撤销 10，used 10，堆 {10}；(1,13) 11；(1,14) 12；(1,15) 13；(1,16) 14——堆 {10,1,1,1,1}，输出 5。撤销发生在第二个任务。
练习 2（改一个条件）：第 05 节的四个任务，总时间 T 从 3 改成 2、再改成 1，报酬各是多少？
展开练习 2 答案
9 和 5。T = 2：(3,2) 的最晚时间变成 2，接下后 3 > 2 撤销最小的 2，剩 {4, 5}；T = 1：只能留一个，撤销到只剩 5。
练习 3（改一个条件）：P2583 的并列规则改成「取编号最大」，2 1 / 4 4 / 1 3 的输出是多少？代码改哪个比较符？
展开练习 3 答案
2。把「严格小于才更新」改成「小于等于就更新」（free[i] <= free[best]），并列时后遇到的（编号更大的）覆盖先前的。这正是第 08 节错误表里那一行——同一处比较符，规则不同答案就不同，以题目页为准。
练习 4（独立实现）：把 AI021 写成函数 max_tasks(tasks)，用两组题面示例、第 04 节的「一个 6 换四个 1」、练习 1、(5, 5) 各写一条断言。
展开练习 4 答案
max_tasks 的参考实现（自带断言）
Pythonimport heapq
def max_tasks(tasks):
# tasks: [(耗时 t, 截止 d)]；串行、不中断，求最多按期完成几个
order = sorted(tasks, key=lambda x: x[1]) # 排序键：截止时刻
heap, used = [], 0 # 已接任务的耗时（存负数 = 大顶堆）、已用时间
for t, d in order:
heapq.heappush(heap, -t) # 先接下
used += t
if used > d: # 超期：撤销耗时最大的
used += heapq.heappop(heap)
return len(heap)
assert max_tasks([(2, 2), (3, 5), (2, 4)]) == 2 # AI021 题面示例 1
assert max_tasks([(5, 3), (4, 2)]) == 0 # 题面示例 2：各自都超期
assert max_tasks([(6, 6), (1, 7), (1, 7), (1, 7), (1, 7)]) == 4 # 第 04 节：撤销 6 换来四个 1
assert max_tasks([(10, 10), (10, 12), (1, 13), (1, 14), (1, 15), (1, 16)]) == 5 # 练习 1
assert max_tasks([(5, 5)]) == 1 # 恰好按期：用 > 不用 >=最后一条断言检查 > 与 >=：恰好按期要算完成。
练习 5（迁移）：把 P3130 写成函数 max_reward(T, tasks)，用第 05 节、练习 2 和「漏掉 min(k, T)」的用例各写一条断言。
展开练习 5 答案
max_reward 的参考实现（自带断言）
Pythonimport heapq
def max_reward(T, tasks):
# tasks: [(最晚处理时间 k, 报酬 l)]；每个任务耗时 1，总时间 T
order = sorted((min(k, T), l) for k, l in tasks) # 最晚时间不超过 T；排序键：最晚时间
heap = [] # 已接任务的报酬（小顶堆）
for deadline, l in order:
heapq.heappush(heap, l) # 先接下
if len(heap) > deadline: # 已接数量就是已用时间；超期撤销报酬最小的
heapq.heappop(heap)
return sum(heap)
assert max_reward(3, [(1, 5), (1, 3), (2, 4), (3, 2)]) == 11 # 第 05 节表
assert max_reward(2, [(1, 5), (1, 3), (2, 4), (3, 2)]) == 9 # 练习 2：T 缩到 2
assert max_reward(1, [(1, 5), (1, 3), (2, 4), (3, 2)]) == 5
assert max_reward(2, [(5, 10), (5, 9), (5, 8)]) == 19 # 漏掉 min(k, T) 会得 27与 max_tasks 只差三处：排序键先取 min(k, T)、堆存报酬不存负数、超期比较用 len(heap)。
10 / 读题要求与复习自评
三道题的要求对照，以及完成本课之后怎么复习
提交前把下表过一遍；题目页的题面与样例是最终依据。
| 项目 | AI021 训练任务调度 | P3130 最大报酬 | P2583 池化资源共享 |
|---|---|---|---|
| 输入 | n；n 行「耗时 截止」 | 「T N」；N 行「最晚时间 报酬」 | 「n m」；剩余空间行；m 行操作 |
| 输出 | 最多完成数 | 最多报酬 | 每次申请的结果，空格分隔 |
| 排序键 | 截止时刻 | min(最晚时间, T) | — |
| 堆里存 / 撤销 | 耗时（存负数）/ 耗时最大 | 报酬 / 报酬最小 | — |
| 示例 | 3 / 2 2 / 3 5 / 2 4 → 2 | 本课自算 T = 3 → 11 | 本课自算 → 1 3 0 1 |
需要对照解法时，展开本页第 07 节的三份完整参考程序。复习与自评：本课的「学习完成检查」六条是自评，不改变题目的通过（AC）状态，本课算完成的条件以页面下方「学习完成检查」处的说明为准。复习时用三个问题自测：① 不看正文，口述接下、超期、撤销的循环，并说出撤销耗时最大的交换论证；② 不看表格，重推「一个 6 换四个 1」；③ 说出 P3130 与 AI021 的三处代码差异。答不出哪一条，就回到对应的节重读，再做第 09 节对应的练习。
11 / 练习
按顺序完成本课的任务
必做题已通过 0/2 道；进阶练习已通过 0/1 道
先预测，再验证：全超期的输入
代码自测自主练习练习重点：拿样例 2 与一组自行构造的输入，先在纸上走完流程；预计用时：10 分钟
完成标准：人工计算结果与程序输出完全一致
需要时查看提示
样例 2 的 (5,3)、(4,2) 各自单独执行都超期：流程会先接下再立刻撤销，最后堆是空的。再自行构造一组「撤销发生在中间」的输入，比如三个任务里第二个被撤销（第 04 节和练习 1 各有一组）。
AI021 · GPU 训练任务调度
必做任务 1练习重点：按截止时刻排序 + 大顶堆撤销；排序与堆操作的总复杂度控制在 O(n log n)；预计用时：30 分钟
完成标准：能整段说出「接下 → 超期 → 撤销耗时最大」的循环，并解释为什么撤销耗时最大
需要时查看提示
排序键应为截止时刻 d，而不是耗时 t。堆里存的是「已接任务的耗时」，已用时间（used）超过当前 d 时弹出耗时最大的并把 used 减回去；恰好等于不算超期。C++/Java 注意 used 累加用 64 位。第 04 节有逐任务表。
P3130 · 在规定时间内获得的最大报酬
必做任务 2练习重点：同一套代码框架：堆里改存报酬，超期时撤销报酬最小的；预计用时：20 分钟
完成标准：能说出这题与 AI021 的两处不同（撤销的键、时间上限 T）
需要时查看提示
第一行是「T N」。每个任务耗时 1，所以「已接数量」就是耗时。除了最晚处理时间，总时间还有上限 T——把最晚时间先与 T 取较小值，两个约束就合成了一个。第 05 节有逐任务表。
P2583 · 池化资源共享
进阶练习 1进阶练习练习重点：申请与释放两类操作的状态维护；并列取编号最小；释放只归还一次；预计用时：20 分钟
完成标准：每条操作后系统状态与人工推演一致
需要时查看提示
这题重在按题目规则精确模拟：申请选剩余不小于且最接近的设备（并列编号最小），失败输出 0；释放把那次申请归还原设备并标记，避免重复归还。逐条规则找到题目中对应的那句话再写分支。第 06 节有逐操作表。
提交结果
提交结果说明与处理方法
- WA
答案错误
三个常见错误：排序键写成耗时 t（应为截止 d）、撤销错了键（AI021 撤销最大耗时、P3130 撤销最小报酬）、P3130 漏了总时间 T 的上限。第 08 节的表给出了每种错误的具体输出
- PE
格式错误
只输出一个整数，不要把堆的内容打出来；P2583 输出空格分隔的一行
- RE
运行错误
空堆时 heappop 会抛异常——本课的写法先入堆再出堆，堆不会空；P2583 释放前查那次申请是否成功
- TLE
超时
每次线性扫描找最大是 O(n²)，n = 10⁵ 时通常无法满足时限；应改用 O(n log n) 的堆操作
- AC
通过
再测三组边界：全部超期（答案 0）、全部都能完成、截止时刻全相同
12 / 学习完成检查
本课学习完成检查
完成本课需要：必做题全部通过，并勾选本课的全部学习完成检查；进阶练习、基础加练与复习题单独统计，不影响完成状态。登录后，勾选记录会保存到账号，并更新课程总览的完成状态。