机器调度模拟
P6087. 机器调度模拟
场次:2026年10月23日-非AI方向 · 来源:CodeFun2000 P6087
题目描述
一共有 项任务要在一台机器上跑完。每项任务带四个量:编号 (互不相同)、优先等级 (数值更大者更靠前)、抵达时刻 、所需时长 。这台机器在任一时刻至多跑一项任务。
调度约定如下。机器一旦空闲,就马上从等候队列里挑一项开始跑;时长 的任务,只要被挑中,就在该时刻立刻结束。某项任务还在跑时,若又有任务抵达,只有新来者的 比正在跑的这项更大,才允许把当前这项挤下去;被挤下去的任务把还没跑完的时间留下来,再放回等候队列。挑下一项时按三层次序比较,从而只有一个结果: 从大到小, 从早到晚,读入时的先后从先到后。被挤下去后再放回队列时,、 和读入先后都保持原来的值,不会改成发生挤占的那个时刻。结束与抵达如果落在同一个时刻,必须先把结束处理完,再把这个时刻抵达的任务收进队列,之后才挑下一项。
解答要求: C 与 C++ 的运行时间上限为 毫秒,其余语言放宽到 毫秒。C 与 C++ 最多占用 兆字节,其余语言最多占用 兆字节。
输入格式
首行一个整数 。后面共有 行,每一行写下四个整数 ,顺次是这项任务的编号、优先等级、抵达时刻和所需时长。各个 彼此不同,读入行的先后会参与挑选时的比较。
数据范围:
- 时刻的加减使用 位有符号整数。
输出格式
只用一行写出 个 ,按结束的先后排好,相邻两个之间隔一个空格。
示例
示例 1
输入:
4
7 2 0 8
9 5 3 2
4 5 3 4
8 1 6 3输出:
9 4 7 8说明: 四项任务按读入先后,编号是 、、、。
时刻 :编号 抵达,队列里只有它,于是开跑,还要跑 。
时刻 :编号 与编号 一同抵达。两者等级都是 ,高于正在跑的 ;编号 在输入里更靠前,所以把编号 挤下去。编号 已跑 ,还剩 ,等级和抵达时刻仍是 与 。编号 开跑,时长 。
时刻 :编号 结束。还在等的是编号 (等级 )和编号 (等级 ),先跑编号 。
时刻 :编号 抵达,等级 并不高于正在跑的 ,只能排队。
时刻 :编号 结束。编号 的等级高于编号 ,接着把剩下的 跑完。
时刻 :编号 结束,编号 开始,再过 结束。
结束顺序是 。
示例 2
输入:
4
6 3 0 4
2 8 1 3
5 1 4 10
9 6 4 2输出:
2 9 6 5说明:
时刻 :编号 开跑,时长 。
时刻 :编号 抵达,等级 高于 ,挤占成功。编号 只跑了 ,还剩 。编号 开跑,将在时刻 结束。
时刻 :编号 结束,同时编号 与编号 抵达。先记下编号 已经结束,再接收新抵达的两项。队列里还有被挤下的编号 (等级 ,剩余 )。等级最高的是编号 ,由它开跑。
时刻 :编号 结束。编号 比编号 更优先,继续把剩余的 跑完。
时刻 :编号 结束,编号 开始,再过 结束。
结束顺序是 。
解题思路
输出是什么:一串「结束顺序」,不是一张时间表
题目只要求按结束的先后输出编号。这一句话决定了整份代码的写法:每结束一项就立刻把它记进答案,时刻本身只在内部用来判断「谁先结束」,不进输出。
为什么不能按分钟推进:时间轴长到 量级
最直观的模拟是「让时间一秒一秒往前走」:每一秒检查有没有任务抵达、正在跑的那项有没有跑完。逻辑上完全正确,但 ,如果任务之间隔着很远,光空转就要走 步, 时更不可能。
真正的信息量其实很少:状态只在「有任务抵达」和「有任务结束」这两个时刻发生变化,中间无论过多久,机器都在跑同一项任务、队列也不变。所以时间应该跳着走:每一步直接跳到下一个事件时刻
事件总数是 个抵达 + 个结束,共 个,于是整份模拟的复杂度只跟 有关,与时刻的大小无关。
三个部件:等候队列、正在跑的那项、抵达指针
- 等候队列:随时要取出「等级最高、其次抵达最早、其次读入最早」的那一项 —— 反复取最优、还要求有序 —— 用堆(Python 的
heapq)。 - 正在跑的那项:只需要知道它的等级 、原始抵达时刻 、读入序号 、编号 ,以及它什么时候跑完
end。剩余时长不必单独维护,因为剩余 =end - 当前时刻。 - 抵达指针
i:把所有任务按抵达时刻排好序,指针指向「还没进队列的第一个」。
三层排序压成一个元组
堆的比较规则就是元组的字典序,所以把「等级降序、抵达升序、读入升序」直接编码成
heapq 是小顶堆,所以等级要取负: 越大 越小,越先被弹出。后两个字段 k 和剩余时长只在弹出时用,不参与比较( 互不相同,比较不会走到它们)。
heapq.heappush(heap, (-r, s, idx, k, d)) # 新抵达
...
nr, s, idx, k, rem = heapq.heappop(heap)
r = -nr # 用的时候再翻回来挤占的判据:只有「严格更大」才挤
题面写的是「新来者的 比正在跑的这项更大」,所以等级相等时不挤,新任务排队等着。同一时刻可能有多项抵达,逐个比较的结果与「先算出这批抵达里最大的 、再与正在跑的比一次」完全等价:
- 若这批里最大的 都不大于正在跑的等级,那么谁都没资格挤;
- 若有一个更大,被挤下去之后的挑选又要按三层序取全场最优,挑出来的必然是这批里的最强者。
所以只要记下「这一轮新抵达的任务里 的最大值」best_new,比一次即可。
被挤下去的那一项必须原样放回:等级、抵达时刻、读入序号都保持任务最初的值,只有剩余时长要换成「结束时刻减去当前时刻」。这三项原值参与排序,改掉任何一项都会改变它下一次被选中的时机。
if cur is not None and best_new > cur[1]:
heapq.heappush(heap, (-cur[1], cur[2], cur[3], cur[4], cur[0] - t))
cur = None同一时刻的三步顺序:先结束 → 再收抵达 → 再挑
题面明确规定「结束与抵达落在同一个时刻,先把结束处理完,再把这个时刻抵达的任务收进队列,之后才挑下一项」。这三步的先后会改变答案:若先收抵达,一个刚好在这一刻跑完的任务会被当成「还在跑」,于是可能被同刻抵达的更高级任务「挤占」,带着剩余 回到队列,等到机器下次空闲才被重新选中,输出里就排到了本来更晚结束的任务后面。
主循环的顺序因此写成:
while 还有抵达 or 队列非空 or 正在跑:
① 把抵达时刻 <= t 的任务全部入队(记下这批里的最大 r)
② 若正在跑,且这批新抵达里有 r 严格更大 -> 挤占,放回队列
③ 若机器空闲,从队列里挑一项开跑(剩余时长为 0 就当场结束)
④ 否则把时间推进到 min(下一个抵达时刻, 当前结束时刻)第 ③ 步里「剩余时长为 0 就当场结束」对应题面的「 的任务被挑中即在该时刻结束」,结束后还要继续挑,所以这一支用了 continue 回到循环开头。
时间推进与收尾
- 队列空了但还有任务没抵达时,直接把时间跳到下一个抵达时刻(
t = tasks[i][0]),不空转; - 下一个抵达时刻早于当前结束时刻 → 时间跳到抵达时刻,处理抵达与挤占;
- 下一个抵达时刻不早于结束时刻 → 时间跳到结束时刻,记下这一项,机器转为空闲。
循环的终止条件是「抵达处理完 + 队列空 + 机器空闲」,此时 项任务都已结束。
实现落点
tasks里每项存成(s, idx, k, r, d)再tasks.sort():按抵达时刻排序,同一时刻自然按读入先后排(idx是第二关键字);- 堆元素里的
rem只在放回队列和首次入队时写入,运行中的剩余时长一律用cur[0] - t现算; - 挤占写回时同样用
cur[0] - t:挤占可能发生在这项任务跑到一半的任意时刻,任何「上一次记下的剩余时长」都已经是旧值; - 每一轮循环开头都要重置
best_new = -inf,否则上一轮的抵达会影响这一轮的挤占判断。
完整代码实现
"""
P6087. 机器调度模拟 - 事件驱动的抢占式优先级调度
M 项任务在一台机器上运行,每项有编号 k、优先等级 r(大者优先)、抵达
时刻 s、所需时长 d。挑选顺序为 (r 降序, s 升序, 读入先后升序)。正在跑
的任务只有在「新抵达者的 r 严格更大」时才被挤下,剩余时长保留、等级与
抵达时刻不变。结束与抵达同刻时,先结束、再收抵达、再挑下一项。
输出所有任务按结束先后的编号。
输入格式:
- 首行 M;
- 随后 M 行,每行 k r s d,读入顺序参与比较。
输出格式:
- 一行 M 个编号,按结束先后,空格分隔。
核心思路:
时间只可能在「抵达」或「结束」时改变,所以不逐秒模拟,而是每次跳到
下一个事件时刻。等候队列用堆,元素取 (-r, s, idx, k, 剩余时长),一个
元组就把三层比较规则表达完。主循环顺序:收抵达 -> 判挤占 -> 空闲则
挑 -> 推进时间。
时间复杂度:O(M log M)
空间复杂度:O(M)
"""
# https://codefun2000.com/p/P6087
import heapq
import sys
# @sample-start
"""
样例输入 1:
4
7 2 0 8
9 5 3 2
4 5 3 4
8 1 6 3
样例输出 1:
9 4 7 8
"""
# @sample-end
# @sample-start
"""
样例输入 2:
4
6 3 0 4
2 8 1 3
5 1 4 10
9 6 4 2
样例输出 2:
2 9 6 5
"""
# @sample-end
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
m = int(data[0])
tasks = []
p = 1
for idx in range(m):
k = int(data[p])
r = int(data[p + 1])
s = int(data[p + 2])
d = int(data[p + 3])
p += 4
tasks.append((s, idx, k, r, d)) # 抵达时刻、读入序号、其余字段
tasks.sort() # 按抵达排序;同刻按读入先后
heap = [] # (-r, s, idx, k, 剩余时长)
cur = None # [结束时刻, r, s, idx, k]
i = 0 # 下一个未抵达的任务
t = 0
res = []
while i < m or heap or cur is not None:
# ① 收下当刻抵达的全部任务,并记下这批里的最高等级
best_new = -10 ** 30
while i < m and tasks[i][0] <= t:
s, idx, k, r, d = tasks[i]
heapq.heappush(heap, (-r, s, idx, k, d))
if r > best_new:
best_new = r
i += 1
# ② 新抵达者等级严格更大 -> 挤占;被挤下的保留原 r、s、idx
if cur is not None and best_new > cur[1]:
heapq.heappush(heap, (-cur[1], cur[2], cur[3], cur[4], cur[0] - t))
cur = None
# ③ 机器空闲则挑一项;剩余时长为 0 的挑中即结束
if cur is None:
if not heap:
t = tasks[i][0] # 队列空,直接跳到下一个抵达
continue
nr, s, idx, k, rem = heapq.heappop(heap)
cur = [t + rem, -nr, s, idx, k]
if rem == 0:
res.append(k)
cur = None
continue
# ④ 推进时间:下一个抵达更早就先去接它,否则等这一项跑完
if i < m and tasks[i][0] < cur[0]:
t = tasks[i][0]
continue
t = cur[0]
res.append(cur[4])
cur = None
print(" ".join(map(str, res)))
def run_tests():
"""运行嵌入的示例,方便本地自测。"""
import io
cases = [
("4\n7 2 0 8\n9 5 3 2\n4 5 3 4\n8 1 6 3\n", "9 4 7 8"),
("4\n6 3 0 4\n2 8 1 3\n5 1 4 10\n9 6 4 2\n", "2 9 6 5"),
# 等级相同不挤占:后到的只能排队
("2\n1 5 0 3\n2 5 2 1\n", "1 2"),
# 时长 0 的任务被挑中即结束
("2\n1 1 0 0\n2 0 0 5\n", "1 2"),
# 结束与抵达同刻:先结束,再收抵达
("3\n1 9 0 2\n2 5 2 2\n3 9 2 1\n", "1 3 2"),
]
for i, (inp, expected) in enumerate(cases, 1):
old_stdin, old_stdout = sys.stdin, sys.stdout
sys.stdin = io.TextIOWrapper(io.BytesIO(inp.encode("utf-8")))
sys.stdout = io.StringIO()
try:
solve()
output = sys.stdout.getvalue().strip()
finally:
sys.stdin, sys.stdout = old_stdin, old_stdout
status = "✓" if output == expected else "✗"
print(f"用例 {i}: 期望={expected!r}, 实际={output!r} {status}")
if __name__ == "__main__":
if len(sys.argv) > 1 and sys.argv[1] == "--test":
run_tests()
else:
solve()示例推演
示例 1:四项任务,读入顺序
先把四项任务摆出来(idx 是读入序号):
| 编号 | 等级 | 抵达 | 时长 | 读入序号 |
|---|---|---|---|---|
时刻 : 抵达队列里只有 ,机器空闲,直接开跑,结束时刻 。
时刻 : 下一个事件是 与 同时抵达(都早于 ),时间跳到 。
- 收抵达:两项都入队,
best_new = 5; - 挤占:,编号 被挤下。它已跑 ,剩余 ,放回队列时仍是 —— 等级 、抵达 、读入 一个都没变;
- 挑下一项:队列里是 与 ,等级与抵达都相同,读入序号 ,所以 先跑,结束时刻 。
时刻 : 下一个抵达是 ,晚于结束时刻 ,所以时间跳到 ,记下 结束(答案:)。机器空闲,队列里 (等级 )与 (等级 ),挑 ,结束时刻 。
时刻 : 下一个抵达 早于 ,时间跳到 。收抵达: 入队,best_new = 1; 不大于正在跑的等级 ,不挤占, 排队。
时刻 : 时间跳到结束时刻 ,记下 结束(答案:)。队列里 (等级 ,剩余 )与 (等级 ,剩余 ),挑 ,结束时刻 。
时刻 : 没有更多抵达,时间跳到 ,记下 结束(答案:)。挑 ,结束时刻 。
时刻 : 记下 结束,答案 。
整个过程只跳了 次时间(),而不是从 走到 ;若某两项之间隔着 个时刻,跳法也只多一次事件。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 逐时刻推进模拟 | 时刻上限 、时长上限 ,空转本身就超时 | ||
| 事件驱动 + 优先队列(最优) | 每次抵达入队一次、每次开始运行出队一次,共 次堆操作 |
时间与 、 的具体大小无关,只与事件个数有关:每项任务首次抵达时入队一次;同一批同时抵达的任务只可能触发一次挤占(这一批处理完就再没有新抵达,下一次挤占只能发生在下一批抵达时),所以被放回队列的次数不超过抵达的批次数,也就不会超过 。堆操作总数是 量级,每次 。按抵达排序同样是 ,与堆同阶。
易错点总结
1. 挤占后把抵达时刻改成当前时刻
写回队列时图省事用 (-cur[1], t, ...) 代替 (-cur[2], ...),这一项就从「最早的抵达者」变成了「刚到的人」。输入
3
1 2 0 10
2 5 3 1
3 2 4 1正确结果是 2 1 3:编号 在时刻 挤下编号 ,时刻 编号 结束后,编号 (等级 、抵达 )与编号 (等级 、抵达 )等级相同,抵达更早的编号 先跑。改掉抵达时刻后编号 变成「抵达 」,让它排在编号 之后,输出 2 3 1。
2. 同一时刻先收抵达、再判结束
把「结束」的判断挪到收抵达之后,已经在此时刻跑完的任务会被当成还在跑,可能被同刻抵达的更高级任务挤占;它带着剩余 回到队列,要等机器下次空闲才被重新挑中。输入
2
1 5 0 3
2 6 3 2正确结果是 1 2(时刻 编号 先结束,再收下编号 )。顺序颠倒后,编号 (等级 )把「还没被判定结束」的编号 挤下,编号 先跑完,输出 2 1。
3. 堆里忘了把等级取负
heapq 是小顶堆。直接 heappush(heap, (r, s, idx, k, rem)) 弹出的就是等级最小的那一项:示例 1 的输出会变成 8 7 9 4(等级 的编号 第一个跑),而不是 9 4 7 8。三个关键字的含义全被翻了过来,整个调度方向正好相反。