第 15 题
答案与解析
第(1)小题
16:30
0 号为 A 型机器，1 号为 B 型机器。B 类作业只能选 1 号；A 类作业比较两台机器已有作业的结束时间，先选结束较早的，时间相同时选编号较小的。实际开始时间取“计划开始时间”和“所选机器的可用时间”中的较大值，再加原作业时长得到实际结束时间。
| 顺序 | 计划时段、类型 | 所选机器 | 实际执行时段 | 分配后0号可用时间 | 分配后1号可用时间 |
|---|---|---|---|---|---|
| 初始 | — | — | — | 空闲 | 空闲 |
| 1 | 07:30～09:00，A | 0 | 07:30～09:00 | 09:00 | 空闲 |
| 2 | 08:00～10:30，B | 1 | 08:00～10:30 | 09:00 | 10:30 |
| 3 | 08:30～11:00，A | 0 | 09:00～11:30 | 11:30 | 10:30 |
| 4 | 10:00～10:30，B | 1 | 10:30～11:00 | 11:30 | 11:00 |
| 5 | 11:00～14:30，A | 1 | 11:00～14:30 | 11:30 | 14:30 |
| 6 | 13:30～14:30，B | 1 | 14:30～15:30 | 11:30 | 15:30 |
| 7 | 14:30～15:00，A | 0 | 14:30～15:00 | 15:00 | 15:30 |
| 8 | 15:00～16:00，B | 1 | 15:30～16:30 | 15:00 | 16:30 |
最后一项 B 类作业必须等待 1 号机器到 15:30 空闲，再执行 1 小时，因此全部作业于 16:30 完成。
第(2)①小题
10000
程序分析
cnt = 60 * 24 # 一天时间的分钟数
b = [0] * (cnt + 1)
w = len(a)
temp = [0] * w
for i in range(w):
s = a[i][0]
b[s] += 1调用 simplesort(a) 后，用开始时间的分钟数作下标统计作业数量。每遇到一项开始时间为 s 的作业，就令 b[s] 加 1，因此第一轮循环结束时，b[s] 表示恰好在第 s 分钟开始的作业数；temp 预留 w 个位置保存排序结果。
for i in range(1, cnt + 1):
b[i] += b[i - 1]循环从小到大累加，处理第 i 项时，b[i－1] 已包含前面各分钟的数量。加上原 b[i] 后，b[i] 就表示开始时间不超过 i 的作业总数，而不再是恰好在第 i 分钟开始的数量。
for i in range(w):
s = a[i][0]
b[s] -= 1
temp[b[s]] = a[i]
return temp若开始时间不超过 s 的作业共有 r 项，则排序后这部分作业占据下标 0～r－1。先将 b[s] 减 1，再写入 temp[b[s]]，就是把当前作业放到该开始时间对应区间尚未占用的最右位置；再次遇到相同开始时间时，存放位置向左移动一格。由计数确定位置，可以得到按开始时间升序排列的结果；相同开始时间的提交顺序，还需要结合遍历方向判断。
加框循环结束后，b[i] 是开始时间不超过 i 的作业总数。各分钟的原始计数非负，所以累加后的 b 数组单调不减；最后一项 b[1440] 已统计当天的全部 w 项作业，等于 10000，也就是数组的最大值。
第(2)②小题
for i in range(w - 1, -1, -1):
共用程序分析见第(2)①小题。
填空分析
最后一个 for i in range(w):
原程序按提交顺序从前向后遍历，但相同开始时间的存放位置却从右向左移动。若作业甲先提交、乙后提交且开始时间相同，甲会先占右侧位置，乙随后放到甲左侧，二者相对顺序被颠倒。
题目要求保留相同开始时间的提交顺序，因此应让后提交的作业先占右侧位置，再把先提交的作业放到左侧。将最后一个循环改为逆序遍历：
for i in range(w - 1, -1, -1):依次访问下标 w－1、w－2、…、0。range 的终点不包含在内，所以结束参数使用 -1，才能处理下标 0；前面的计数循环不需要修改。
第(3)小题
p >= m
seats[idx][0] += duration
seats[idx][1] = p
程序分析
seatcount = m + n
seats = []
for i in range(seatcount):
seats.append([-1, i + 1]) # seats[i]初始化为[-1, i + 1]
seats[seatcount - 1][1] = -1
head = 0主程序先取得排序后的 data，再调用 allocate(data, m, n)。seats 的下标对应机器编号，seats[i][1] 保存后继机器的编号。初始化后，head 指向 0，各结点依次相连，形成 0→1→…→m＋n－1 的静态链表；末结点的后继为 -1，表示链表结束。seats[i][0] 初值为 -1，其时间含义可由后续更新语句确定。
for d in data:
start, end, ptype = d[0], d[1], d[2]
duration = end - start
...外层循环按已排好的顺序逐项分配作业。start、end 是原定开始和结束时间，duration 是必须保持不变的执行时长；ptype 决定机器类型限制。每轮依次选择机器、暂时摘下结点、更新时间，再寻找重新插入的位置。
p = head
pre = idx = -1
while p != -1:
if ptype == "A" or ①:
idx = p
break # 退出循环
pre = p
p = seats[p][1]p 从表头出发，沿 seats[p][1] 逐结点访问；pre 随之记录前驱。遇到第一个满足条件的结点便把编号存入 idx 并停止。已有条件允许 A 类作业选取当前机器，另一类作业的筛选条件由空①补足。
if pre == -1:
head = seats[idx][1]
else:
seats[pre][1] = seats[idx][1]pre＝-1 表示选中表头，令 head 越过 idx；否则让前驱直接指向 idx 的后继。这两种操作都把 idx 暂时从链表中摘下，seats[idx] 中保存的数据仍然存在。
if seats[idx][0] <= start:
seats[idx][0] = end
else:
②程序把 seats[idx][0] 与作业开始时间比较，若不晚于 start，便将其更新为 end。由此可确定，第 0 项记录该机器已有作业的结束时间，也就是机器可用时间；初值 -1 表示初始空闲。else 对应机器仍被占用，新的结束时间需要在空②中按延期规则更新。
pre, p = -1, head
while p != -1:
v, k = seats[p][0], seats[idx][0]
if v < k or (v == k and p < idx):
pre = p
p = seats[p][1]
else:
break更新后，从剩余链表的表头重新查找插入位置。这里 v、k 分别是当前结点和待插入机器的可用时间。可用时间更早，或时间相同且编号更小的结点，应排在 idx 前面，因此继续向后找。停止时，pre 是应位于 idx 前面的结点，p 是应位于 idx 后面的结点；p＝-1 表示插在表尾。
③
if pre == -1:
head = idx
else:
seats[pre][1] = idx已有语句把表头或前驱指向 idx，完成插入的前半段连接。空③还需处理 idx 自身的后继，使后面的结点仍可沿链表访问。
填空分析
①
A 型机器编号为 0～m－1，B 型机器编号从 m 开始。已有 ptype == "A" 允许 A 类作业选择任意机器；对 B 类作业，只需判断当前编号是否属于 B 型范围，填 p >= m。p 是遍历到的机器编号，本身已在有效编号范围内。
②
进入 else 时，所选机器已有作业的结束时间晚于 start，新作业要等到 seats[idx][0] 时刻才能开始。执行时长保持为 duration，因此新结束时间＝旧结束时间＋duration，填写：
seats[idx][0] += duration③
查找结束时，插入关系应为“pre→idx→p”；若没有前驱，则 idx 成为表头。后面的已知语句负责让 pre 或 head 指向 idx，因此本空应先让 idx 指向新的后继 p：
seats[idx][1] = p插在表尾或剩余链表为空时，p＝-1，同一语句也能正确终止链表。这样重新插入后，链表仍按“可用时间优先、编号次之”升序排列。下一轮从表头选择第一个类型合适的机器，就能落实题目的两级优先规则。
问题反馈
解析有疑问或显示异常？请先复制题目信息，再打开反馈表单填写。
题目编号：2026_04_G3_shaoxingzhenduan_q015