从问题到算法:先说清什么要保持成立¶
换个平局条件,还是同一个算法吗?¶
当前最早任务记为 A,下一项 B 与它同一时间到达。若约定先出现的优先,用严格的 < 时 A 留下。若约定后来者优先,遇到相等可以更新为 B。比较符号对应的是题目规则,不能只靠最终最小值判断实现是否正确。
怎样用一句话说明扫描到中间时仍然正确?
记录的是已检查项中最早、且符合平局规则的任务。再处理一项时只有比较与更新两种动作,都要保持这条性质。
先修:会读变量、条件和循环。
读完能做:把一句需求写成可检验的输入、输出和约束,并解释循环每处理一项后,为什么手里拿着的仍是目前最早的那项。这条始终要保持的规则叫**循环不变量**。
假设站点收到了三个任务,提交时刻分别是 12、9、15。你要找最早的任务。输入是一列任务,输出是一个任务,约束是空表没有答案,时间相同取先出现在输入里的任务。明确最后一条,才知道比较时该用 < 还是 <=。
def earliest(tasks):
if not tasks:
return None
best = tasks[0]
for task in tasks[1:]:
if task["submitted"] < best["submitted"]:
best = task
return best
best 的**循环不变量**是:每次处理完一项,它都是已经检查过的任务里最早的一项,时间相同保留第一项。第一次处理前只检查了首项,条件成立。下一项更早就换掉,否则保留,条件继续成立。循环结束时,已经检查的集合就是整个输入。这个解释也暴露了空表需要单独处理的原因。
tasks[1:] 表示从第 2 项取到列表末尾。这种取一段列表的写法叫**切片**,Python 会把结果放到一份新列表。数据很多时,可以改用位置编号逐项读原列表,省下一份复制的空间。若还要反复取下一项最早的任务,可以用每次挑最早一项的优先队列。
自测¶
输入的提交时刻为 12、9、9、15。逐项写出当前候选。如果条件改成 <=,最终保留哪一项?
参考思路
严格比较时保留第一个时刻为 9 的任务。改成非严格比较后,第二个时刻为 9 的任务会覆盖前一个。两种规则都找到最小值,但对应不同的并列约定。