01 / 本课学习路线
本课学习路线
阅读与推演约 105 分钟,练习约 60 分钟,进阶练习另需约 45 分钟
02 / 学习目标与先修自测
学完本课你能做什么,以及开始前需要会什么
写代码前把排序键写成一行注释,标清每层字段、方向和并列规则,再逐项实现。
| 学完后能做的事 | 正文位置 | 检查方式 |
|---|---|---|
| 把「A 升序、A 相同 B 升序、都相同保持输入顺序」写成键元组,并说出哪一层由稳定排序保证 | 第 03、04 节 | 自查第 2、4 条、练习 1 |
| 数值降序用取负、按题意处理字符串大小写;需要字符串降序时,按各字段方向选择复合键或两次稳定排序 | 第 05 节 | 自查第 3 条、练习 3 |
| 把容量串、未补零时间解析成可比较的数值,解析单独成函数 | 第 06 节 | 自查第 5 条、练习 5 |
| 不看参考代码写出 P2550、P2556 并通过(AC) | 第 07 节 | 必做任务 2、3 |
| 用一个具体输入说明比较函数不传递或两次排序顺序反了会错在哪 | 第 08 节 | 练习 2 |
先修自测:下面 5 题请先自己写答案,再展开对照。答不出的按括号里的位置补看再回来。本课假定你会模块 1 的读入与输出、字典与列表操作。
| 题号 | 题目 | 补看位置 |
|---|---|---|
| 自测 1 | (165, 60) < (170, 55) 与 (165, 60) < (165, 55) 各是真还是假? | 元组 |
| 自测 2 | sorted([3, 1, 2], key=lambda x: -x) 得到什么?key 函数返回的值用来做什么? | 列表常用操作 |
| 自测 3 | sorted([(1, "b"), (1, "a"), (0, "c")], key=lambda t: t[0]) 里两个 1 的相对顺序会变吗? | 列表常用操作 |
| 自测 4 | "Beta".lower() 是什么?"Beta" < "alpha" 为什么是真? | 字符串 |
| 自测 5 | int("01") 与 int("1") 相等吗?"9" > "10" 为什么是真? | 数字与运算符 |
展开先修自测答案
自测 1:真;假。元组比较先比第 0 个分量,相等再比第 1 个——多级排序键就是靠这一点写成一个元组的。
自测 2:[3, 2, 1]。key 的返回值只用来决定顺序,元素本身不变;取负就得到数值降序。
自测 3:不会变,仍是 (1, "b") 在 (1, "a") 前。Python 的排序是稳定的:键相等的元素保持原来的相对顺序。
自测 4:"beta"。字符串按字符编码逐位比较,大写 B 的编码 66 小于小写 a 的 97,所以 "Beta" < "alpha"——这就是 P2556 要求「转小写后比较」的原因。
自测 5:相等(int 忽略前导零)。"9" > "10" 为真是因为字符串逐位比较:第一位 9 比 1 大,不看长度——按原始字符串比较时间就会错。
03 / 概念与术语
排序键、方向、并列规则、稳定排序、归一化、传递性
复合排序题只有六个名词。把它们和代码写法一一对应起来,后面每道题都按同一套写。
| 术语 | 含义 | 代码写法 |
|---|---|---|
| 排序键 | 给 sorted / sort 的 key 函数返回的值,元素按它比较 | key=lambda p: (p[0], p[1]) |
| 层 | 键元组的每个分量,前面的层优先 | 第 0 个分量先比,相等再比第 1 个 |
| 方向 | 某一层是升序还是降序 | 升序直接放;数值降序放相反数 -x |
| 并列规则 | 前面所有层都相等时,题目规定的先后 | 写成下一层;「保持输入顺序」这一层可以不写,由稳定性保证 |
| 稳定排序 | 键相等的元素保持原来的相对顺序 | Python 的 sorted / list.sort 都稳定 |
| 归一化 | 把不同写法的同一个量换算成同一种可比较的数值 | 时间 → 毫秒数;容量 → 以 M 为单位的整数 |
| 传递性 | a<b 且 b<c 时必须 a<c;自定义比较函数不满足时结果依赖输入顺序 | 能用键元组就不用比较函数 |
比较函数必须满足传递性
a<b、b<c 就必须 a<c。比较函数不满足传递性时,排序结果会依赖输入的排列顺序,在不同测试用例中表现不一致——这是最难排查的一类答案错误(WA)。能用键元组就不用比较函数。
04 / 从规则到排序键
P2550 身高体重排序:三层键与两个题面示例的逐步排序
题面:第一行 n,第二行 n 个身高,第三行 n 个体重;按身高由低到高,身高相同按体重由轻到重,都相同保持编号顺序;输出排序后的学生编号(从 1 起),题面示例里编号连着输出、没有分隔符。
先写排序键注释,再写代码
# 排序键:(身高 升序, 体重 升序);都相同保持编号顺序 → 稳定排序保证 # 输出:排序后的编号,无分隔符
| 编号 | 身高 | 体重 | 键 (身高, 体重) | 排序后的位置 |
|---|---|---|---|---|
| 1 | 100 | 40 | (100, 40) | 第 2 |
| 2 | 100 | 30 | (100, 30) | 第 1(身高并列,体重 30 < 40) |
| 3 | 120 | 60 | (120, 60) | 第 3 |
| 4 | 130 | 50 | (130, 50) | 第 4 |
输出 2134,与题面示例一致。编号 1 和 2 身高相同,由第二层体重决定先后。
| 编号 | 键 (身高, 体重) | 排序后的位置 | 依据 |
|---|---|---|---|
| 1 | (90, 45) | 第 1 | 与编号 3 的键相等,稳定排序保持输入顺序:1 在 3 前 |
| 3 | (90, 45) | 第 2 | 同上 |
| 2 | (110, 60) | 第 3 | 身高最高 |
输出 132。第三层「保持编号顺序」没有写进键,靠稳定排序保证;显式写成 (身高, 体重, 编号) 结果相同——第 09 节练习 4 两种写法都验证。
本课自测用的四人例:1:(170,60) 2:(165,60) 3:(170,55) 4:(165,60)
键: (身高, 体重)
排序: 2:(165,60) → 4:(165,60) → 3:(170,55) → 1:(170,60)
↑ 165<170 先出;两个 (165,60) 并列,稳定性保住 2 在 4 前
↑ 170 组内 55<60,3 在 1 前
输出: 2 4 3 1(自测里按列表比较)05 / 混合方向与字符串并列
P2556 开源项目热榜:加权热度降序,并列按名字转小写的字典序
题面:第一行 N;第二行 5 个权重(关注、收藏、复制(fork)、问题(issue)、合并请求(MR));随后 N 行「名字 关注数 收藏数 复制数 问题数 合并请求数」。热度 = 五项加权和;按热度降序输出名字,热度相等按名字转全小写后的字典序。
先写排序键注释
# 热度 = w1·watch + w2·star + w3·fork + w4·issue + w5·mr # 排序键:(-热度 ↓, 名字.lower() ↑);输出原名字
| 项目 | 热度计算 | 热度 | 键 (-热度, 小写名) | 输出顺序 |
|---|---|---|---|---|
| alpha | 1×1 + 2×2 + 3×3 + 4×4 + 5×5 | 55 | (−55, alpha) | 第 1 |
| Beta | 同上 | 55 | (−55, beta) | 第 2(并列,alpha < beta) |
| gamma | 1×5 + 2×4 + 3×3 + 4×2 + 5×1 | 35 | (−35, gamma) | 第 3 |
输出 alpha / Beta / gamma。如果并列时不转小写、直接比较原名字:大写 B 的编码 66 小于小写 a 的 97,Beta 会排到 alpha 前面——第 08 节的错误表给出这个输出。题面样例在题目页查看;本例为自拟。
字符串没法取负:需要「字符串降序」时用两次稳定排序——先按次要键排一遍,再按主要键排一遍(后一次排序不会打乱前一次留下的并列顺序)。「热度降序、名称字典序降序」就是:先按名称降序排一次(reverse=True),再按热度降序稳定排一次。顺序必须从次要到主要,反了则上一层的结果会被打乱(每一层都是降序时,也可以直接对键元组整体用 reverse=True)。
补充学习(选学)稳定排序与两次排序的配合约 4 分钟字符串降序做不了取负时的正规解法
稳定排序的定义:相等元素保持原有相对顺序。利用它可以把多层排序拆成多次单层排序——从最次要的键排到最主要的键,每一层都不会打乱上一层排好的并列关系。
「热度降序、名称字典序降序」这种两层都没法进一个键的情况:先按名称降序排一次(reverse=True),再按热度降序稳定排一次。顺序必须从次要到主要,顺序反了,上一层的结果会被打乱。
06 / 排序前的归一化
P2553 磁盘容量与 P2554 日志时间:先换算成同一种数值再比较
两道进阶题的排序键都只有一层,难点全在解析:容量单位可以重复出现(3M12G9M),时间可能没补零(1:1:1.1)。解析单独写成函数,排序主体才不被细节干扰。
| 容量串 | 逐段折算 | 以 M 为单位 | 排序后位置 |
|---|---|---|---|
| 20M | 20 | 20 | 第 1 |
| 3G | 3×1024 | 3072 | 第 2 |
| 3M12G9M | 3 + 12×1024 + 9 | 12300 | 第 3 |
| 1T | 1×1024×1024 | 1048576 | 第 4 |
| 10G6T | 10×1024 + 6×1024×1024 | 6301696 | 第 5 |
输出 20M / 3G / 3M12G9M / 1T / 10G6T,与题面示例一致。3M12G9M 与 12M12G 相等(都是 12300M),两者同时出现时按输入顺序输出——题面明确要求稳定排序。
| 时间串 | 解析后的四段 | 毫秒数 | 说明 |
|---|---|---|---|
| 01:01:01.001 | 1, 1, 1, 1 | 3661001 | 补了零 |
| 1:1:1.1 | 1, 1, 1, 1 | 3661001 | 没补零,int() 自动忽略前导零,与上一行相等 |
| 9:0:0.0 | 9, 0, 0, 0 | 32400000 | — |
| 10:0:0.0 | 10, 0, 0, 0 | 36000000 | — |
按毫秒数排序:01:01:01.001、1:1:1.1(相等,保持输入顺序)、9:0:0.0、10:0:0.0。按原始字符串排序会得到 01:01:01.001、10:0:0.0、1:1:1.1、9:0:0.0——因为字符串逐位比较,"10" 的第一位 1 小于 "9"。
补充学习(选学)归一化解析:时间与容量两个场景约 5 分钟补零位、单位折算,解析函数怎么拆
日志时间 H:M:S.N(时:分:秒.毫秒)四段都可能没补零:"9:0:0.0" 按字符串比较时 "9" > "1",会排到 "10:0:0.0" 后面去。正确做法是解析成毫秒数:((H×60+M)×60+S)×1000+N,再按数值比较。
磁盘容量 3M12G9M 单位可以重复出现:逐段扫描,遇到单位就把累计的数字按 1T=1024G、1G=1024M 折算成 M 累加。3M12G9M = 12×1024 + 12 = 12300M,和 12M12G 相等。完成容量解析和单位换算后,再按统一数值排序并保持相等项的原顺序。
07 / 从步骤到程序
解析 → 键 → 输出三段式,四道题的完整参考程序
先对照三段式模板自己写完并提交,再展开对照。
解析 → 键 → 输出 三段式模板
Pythonimport sys
def parse(line: str):
# 步骤 1:将一行原始输入解析为 (可比较字段..., 原始编号)
...
def sort_key(item):
# 步骤 2:按优先级逐层构造排序键,每层标注方向;数值降序取负
...
def main():
data = sys.stdin.read().splitlines()
items = [parse(x) for x in data if x.strip()]
items.sort(key=sort_key)
# 步骤 3:根据题目要求输出编号或原值,并核对分隔符是空格还是换行
...
main()解析与归一化(补零位、单位换算)全部做在 parse 里;sort_key 逐层写并标注方向;输出前确认打印的是编号还是原值。
| 题目 | 解析 | 排序键 | 输出 |
|---|---|---|---|
| P2550 | 三行 → (身高, 体重, 编号) | (身高, 体重) | 编号连写,无分隔符 |
| P2556 | 每行 → (名字, 加权热度) | (-热度, 名字.lower()) | 每行一个原名字 |
| P2553 | 容量串 → 以 M 为单位的整数 | 折算值(稳定) | 每行一个原容量串 |
| P2554 | 时间串 → 毫秒数 | 毫秒数(稳定) | 每行一个原时间串 |
展开完整参考程序 1:P2550 身高体重排序(先自己写完并提交一次,再展开对照)
完整程序:P2550(标准输入 → 标准输出)
Pythonimport sys
data = sys.stdin.read().split()
n = int(data[0])
heights = [int(x) for x in data[1:1 + n]]
weights = [int(x) for x in data[1 + n:1 + 2 * n]]
people = [(heights[i], weights[i], i + 1) for i in range(n)] # (身高, 体重, 编号从 1 起)
people.sort(key=lambda p: (p[0], p[1])) # 身高升序、体重升序;编号顺序由稳定排序保持
print("".join(str(p[2]) for p in people)) # 题面示例:编号连着输出,没有分隔符自测用例:题面两个示例(2134、132)与本课四人例(2431)。输出没有分隔符是题面示例给出的格式;把它写成空格分隔会答案错误。
展开完整参考程序 2:P2556 开源项目热榜
完整程序:P2556(标准输入 → 标准输出)
Pythonimport sys
lines = sys.stdin.read().split("\n")
n = int(lines[0])
weights = [int(x) for x in lines[1].split()] # 5 个权重:关注、收藏、fork、issue、MR
projects = []
for k in range(2, 2 + n):
parts = lines[k].split()
name = parts[0]
counts = [int(x) for x in parts[1:6]]
heat = sum(w * c for w, c in zip(weights, counts)) # 加权求和
projects.append((name, heat))
# 热度降序 → 取负;并列按名字转小写后的字典序升序;输出仍用原名字
projects.sort(key=lambda p: (-p[1], p[0].lower()))
print("\n".join(name for name, _ in projects))自测用例:第 05 节自拟输入(alpha / Beta / gamma)。题目页参考题解的排序键是 (-total, name.lower()),与本程序相同。
展开完整参考程序 3:P2553 磁盘容量(进阶)
完整程序:P2553(标准输入 → 标准输出)
Pythonimport sys
lines = sys.stdin.read().split("\n")
n = int(lines[0])
disks = lines[1:1 + n]
UNIT = {"M": 1, "G": 1024, "T": 1024 * 1024}
def to_mb(s):
total, num = 0, ""
for ch in s:
if ch.isdigit():
num += ch # 累积数字
else:
total += int(num) * UNIT[ch] # 遇到单位就折算成 M 累加
num = ""
return total
order = sorted(range(n), key=lambda i: to_mb(disks[i])) # 只按折算值排;相等的保持原顺序(稳定)
print("\n".join(disks[i] for i in order))自测用例:题面示例(20M / 3G / 3M12G9M / 1T / 10G6T)。sorted(range(n), key=...) 排的是下标,相等折算值保持原下标顺序,正是题面要求的稳定排序;参考题解把下标显式写进键 (convert(s), i),效果相同。
展开完整参考程序 4:P2554 日志时间排序(进阶)
完整程序:P2554(标准输入 → 标准输出)
Pythonimport sys
data = sys.stdin.read().split()
n = int(data[0])
logs = data[1:1 + n] # 同一行或每行一个都能读到
def to_ms(t):
h, m, rest = t.split(":")
s, ms = rest.split(".")
return ((int(h) * 60 + int(m)) * 60 + int(s)) * 1000 + int(ms) # int() 自动忽略前导零
order = sorted(range(n), key=lambda i: to_ms(logs[i])) # 相等时间保持输入顺序
print("\n".join(logs[i] for i in order))题面写「第二行为 N 个时间」,参考题解按每行一个读取——本程序一次读完按空白切分,两种排版都能读;输出每行一个原始时间串。自测用例:第 06 节表里的四个时间,以及练习 5 的三个时间。
08 / 边界、反例与复杂度
错误做法在具体输入上各输出什么
下面每一行都是一个具体的错误程序,给出输入、错误输出与正确输出;把参考程序改成对应写法就能复现。
| 错误做法 | 输入 | 错误输出 | 正确输出 | 判题结果 |
|---|---|---|---|---|
| P2550 编号用空格分隔输出 | 题面示例 1 | 2 1 3 4 | 2134 | 答案错误(WA)或格式错误(PE) |
| P2550 只按身高排、漏体重层 | 题面示例 1 | 1234(1、2 身高并列时保持输入顺序) | 2134 | 答案错误(WA) |
| P2556 并列时不转小写 | 第 05 节自拟输入 | Beta / alpha / gamma | alpha / Beta / gamma | 答案错误(WA) |
| P2554 按原始字符串排序 | 第 06 节四个时间 | 01:01:01.001 / 10:0:0.0 / 1:1:1.1 / 9:0:0.0 | 01:01:01.001 / 1:1:1.1 / 9:0:0.0 / 10:0:0.0 | 答案错误(WA) |
| P2553 只看最后一个单位 | 3M12G9M 当作 9M | 3M12G9M 排到 20M 前 | 20M / 3G / 3M12G9M / … | 答案错误(WA) |
| 两次排序顺序反了(先按热度、再按名称降序) | 第 05 节自拟输入,规则改为热度降序 + 名称降序 | 最后一次按名称排序覆盖了热度顺序:gamma / Beta / alpha | Beta / alpha / gamma(先按名称排、再按热度排,见练习 3) | 答案错误(WA) |
| 自定义比较函数不满足传递性 | 任何有三个以上并列的输入 | 不同测试用例结果不一致 | 改用键元组 | 部分用例答案错误(WA) |
第二行的错误输出计算:只按身高排时 (100,·)1、(100,·)2 保持输入顺序 → 1 2 3 4。
| 题目 | 输入规模 | 参考程序的时间与空间 | 结论 |
|---|---|---|---|
| P2550 | n 个学生(以题目页为准) | O(n log n) 排序;O(n) 空间 | 排序一次 |
| P2556 | N < 100 | O(N log N);O(N) | 规模很小,一次排序 |
| P2553 | n ≤ 100,串长 < 30 | 解析 O(总长) + 排序 O(n log n) | 规模很小,一次排序 |
| P2554 | N ≤ 10000 | O(N log N);O(N) | 一次排序远小于时限 |
排序本身 O(n log n) 按量级估算远小于时限;若超时,先查解析里是否嵌套了重复扫描(例如对每条记录再扫一遍全部记录)。
09 / 渐进练习与参考答案
跟做 → 改一个条件 → 独立实现 → 迁移
每题先在纸上或文件里做完,再展开答案。
练习 1(跟做):不运行程序,按第 04 节表的格式写出 P2550 输入「n=3,身高 90 110 90,体重 45 60 45」每个人的键和排序后的位置,并说出哪一步用到了稳定性。
展开练习 1 答案
编号 1 (90,45)、编号 2 (110,60)、编号 3 (90,45)。排序:1 与 3 键相等 → 稳定排序保持 1 在 3 前 → 第 1、第 2;2 身高最高 → 第 3。输出 132。稳定性用在 1 与 3 的先后:如果排序不稳定(或自己写的排序打乱了相等元素),可能输出 312。
练习 2(改一个条件):把 P2550 的规则改成「身高由高到低、同身高按体重由轻到重、都相同保持编号顺序」,排序键怎么写?题面示例 1 的输出变成什么?
展开练习 2 答案
键 (-身高, 体重):身高降序取负,体重仍升序。示例 1:4 (−130,50)、3 (−120,60)、2 (−100,30)、1 (−100,40) → 输出 4321。做错最常见的原因:把体重也取了负(变成由重到轻)。
练习 3(改一个条件):P2556 的并列规则改成「热度相等按名字转小写后的字典序**降序**」,不能取负的字符串怎么办?用第 05 节的自拟输入写出输出。
展开练习 3 答案
两次稳定排序:先按 name.lower() 降序排一次(reverse=True),再按热度降序稳定排一次(键 -heat)。自拟输入:并列的 alpha、Beta 按小写降序是 Beta、alpha;再按热度排后 gamma 仍在最后 → 输出 Beta / alpha / gamma。顺序反了(先热度后名字)会把热度顺序打乱。
练习 4(独立实现):完成「代码自测」任务的 sort_key 让断言通过;再用显式写进编号的键 (身高, 体重, 编号) 跑一遍,确认结果相同。
展开练习 4 答案
sort_key 的参考实现(自带断言,两种写法)
Pythondef sort_key(item):
height, weight, _idx = item
return (height, weight) # 编号那一层交给 sorted 的稳定性
people = [(170, 60, 1), (165, 60, 2), (170, 55, 3), (165, 60, 4)]
assert sort_key((165, 60, 2)) < sort_key((170, 55, 3))
got = [p[2] for p in sorted(people, key=sort_key)]
assert got == [2, 4, 3, 1], got
# 显式把编号写进键,结果相同:
assert [p[2] for p in sorted(people, key=lambda p: (p[0], p[1], p[2]))] == [2, 4, 3, 1]返回 (身高, 体重) 即可,编号层由稳定排序保证;显式返回三元组结果相同——两种写法的断言都在这段代码里。
练习 5(迁移):P2554 输入三个时间 1:1:1.1、01:01:01.001、0:59:59.999,输出顺序是什么?前两个为什么按这个顺序?
展开练习 5 答案
毫秒数:3661001、3661001、3599999 → 输出 0:59:59.999 / 1:1:1.1 / 01:01:01.001。前两个毫秒数相等,题面要求相等时间保持输入顺序,所以 1:1:1.1(先输入)在前——不能因为它「看起来没补零」就调换。这也是为什么解析要输出原始字符串而不是解析后的值。
10 / 读题要求与复习自评
四道题的要求对照,以及完成本课之后怎么复习
提交前把下表过一遍;题目页的题面与样例是最终依据。
| 项目 | P2550 身高体重排序 | P2556 开源项目热榜 | P2553 磁盘容量 | P2554 日志时间排序 |
|---|---|---|---|---|
| 输入 | n;n 个身高;n 个体重 | N;5 个权重;N 行「名字 + 5 个数」 | n;n 行容量串 | N;N 个时间串(同一行或每行一个) |
| 排序键 | (身高↑, 体重↑) | (−热度, 名字小写↑) | 折算成 M 的整数↑ | 毫秒数↑ |
| 并列规则 | 保持编号顺序(稳定) | 名字转小写字典序 | 保持输入顺序(稳定) | 保持输入顺序(稳定) |
| 输出 | 编号连写,无分隔符 | 每行一个原名字 | 每行一个原容量串 | 每行一个原时间串 |
| 样例 | 2134、132 | 题目页为准(自拟见第 05 节) | 20M / 3G / 3M12G9M / 1T / 10G6T | 题目页为准(自拟见第 06 节) |
题解入口:需要对照解法时,先展开本课第 07 节的四份完整参考程序;四道题的题目页另有思路与 Python / Java / C++ 参考代码,可在题目页查看。复习与自评:本课算完成 = 两道必做题 P2550、P2556 都通过判题,并勾选全部六条「学习完成检查」;进阶练习与复习题不影响完成状态。六条检查是自评,不改变题目的通过(AC)状态。复习时用三个问题自测:① 不看正文,写出 P2556 的排序键注释并说明每一项的方向;② 不看表格,把 3M12G9M 与 10G6T 折算成 M;③ 说出稳定排序的定义,以及 P2550 哪一层靠它保证。答不出哪一条,就回到对应的节重读,再做第 09 节对应的练习。
11 / 练习
按顺序完成本课的任务
必做题已通过 0/2 道;进阶练习已通过 0/2 道
实现三层排序键并验证稳定性(sort_key)
必做任务 1:代码自测自主练习练习重点:把「身高升序、体重升序、编号保序」翻译成键元组;预计用时:10 分钟
完成标准:能说出稳定排序保证了哪一层规则
需要时查看提示
sort_key 返回 (身高, 体重) 就够——编号层由 sorted 的稳定性保证;显式返回 (身高, 体重, 编号) 也对。断言里两个 (165,60) 的顺序就是检验点。参考实现在第 09 节练习 4 的展开区。
自测代码(复制到你的代码文件中运行,检查输出是否一致)
def sort_key(item):
# item = (身高, 体重, 原始编号)
# 请在这里实现:身高升序、体重升序;稳定性交给 sorted 或显式写进键
...
people = [(170, 60, 1), (165, 60, 2), (170, 55, 3), (165, 60, 4)]
# 先直接检验你的键:身高低的应排前面
assert sort_key((165, 60, 2)) < sort_key((170, 55, 3))
# 再检验整体排序:两个 (165,60) 并列时 2 在 4 前——这就是稳定性在起作用
got = [p[2] for p in sorted(people, key=sort_key)]
assert got == [2, 4, 3, 1], gotP2550 · 身高体重排序
必做任务 2练习重点:身高升序、体重升序、都相同保持编号顺序,输出编号;预计用时:20 分钟
完成标准:能解释为什么第三层可以交给稳定排序
需要时查看提示
把 (身高, 体重, 编号) 一起存进列表,排序键取前两项。输出的是编号不是身高,且题面示例里编号连着输出、没有分隔符——打印前再读一遍题目说明的输出段。第 04 节有两个示例的逐步表。
P2556 · 开源项目热榜
必做任务 3练习重点:五维加权求热度;热度降序、并列按名称转小写后的字典序;预计用时:30 分钟
完成标准:能写出 (-热度, 名称转小写) 这种混合方向键并解释每一项
需要时查看提示
权重与五个维度的数按题目说明的顺序读入,热度 = 加权和。第二层是「转小写后的字典序」——比较前先转小写(lower),输出仍用原名称。第 05 节的自拟输入可以自测并列。
P2553 · 磁盘容量
进阶练习 1进阶练习练习重点:把 3M12G9M 式容量串折算成统一单位后稳定排序;预计用时:25 分钟
完成标准:能说出 3M12G9M 折算成多少 M,并保证相等容量维持原顺序
需要时查看提示
逐字符扫描:累数字,遇 M/G/T 按 1、1024、1024×1024 折成 M 累加。排序键是折算值;题目说明明确要求保持原位置,sorted 的稳定性天然满足。第 06 节有题面示例的折算表。
P2554 · 日志时间排序
进阶练习 2进阶练习练习重点:H:M:S.N 未补零的时间解析成毫秒后排序;预计用时:20 分钟
完成标准:能解释为什么不能按原始字符串直接比较
需要时查看提示
按 : 和 . 拆成四段,int() 会自动忽略前导零,折算成毫秒再排。输出原始日志行,不是解析后的数值;相等时间保持输入顺序。第 06 节有四个时间的换算表。
提交结果
提交结果说明与处理方法
- WA
答案错误
多数答案错误来自并列层漏读:身高相同的两人顺序不对、热度相同的项目没按小写字典序——回到题目说明把每一层规则标出来;第 08 节的表给出了每种错误的具体输出
- PE
格式错误
输出编号还是原值、空格还是换行,逐项对样例;P2550 的编号连写、行末多一个空格也是错
- RE
运行错误
解析函数遇到空行或末尾换行会报错:按行拆分(splitlines)后过滤空串再解析
- TLE
超时
排序本身 O(n log n) 远在时限内;超时先查解析里是否嵌套了重复扫描
- AC
通过
不看代码再把这题的排序键写一遍注释,下一课「堆与 Top-K 问题」堆的比较元组会直接用到同一套写法
12 / 学习完成检查
本课学习完成检查
完成本课需要:必做题全部通过,并勾选本课的全部学习完成检查;进阶练习、基础加练与复习题单独统计,不影响完成状态。登录后,勾选记录会保存到账号,并更新课程总览的完成状态。