第 12 章 自定义排序¶
配套例题：BISHI21 【模板】排序、BISHI22 分数线划定、BISHI23 小红书推荐系统、 BISHI24 谐距下标对、BISHI25 最大 FST 距离、BISHI12 元素方碑 来源：菜鸟教程 Python3 列表
sort、sorted、operator模块、lambda；S4 模板
排序是笔试题里出现频率最高的操作，没有之一。而 Python 的排序和 C++ 的
std::sort 思路完全不同：C++ 给的是「比较函数」，Python 给的是「关键字函数」。
这个差异不是语法糖，而是性能量级的差别——用错了会从 \(O(n \log n)\) 次比较
退化成 \(O(n \log n)\) 次 Python 函数调用。本章是第一部分的重点章，会把
key、稳定性、cmp_to_key 三件事讲透。
12.1 sorted 与 list.sort¶
| 项 | sorted(x) |
x.sort() |
|---|---|---|
| 输入 | 任意可迭代对象（list/tuple/set/dict/生成器） |
只能是 list |
| 返回值 | 新的 list |
None |
| 原对象 | 不变 | 被改掉 |
| 额外内存 | \(O(n)\) | \(O(n)\) 的临时空间（Timsort 需要） |
| 速度 | 略慢（要先建列表） | 略快 |
sorted("cba") # ['a', 'b', 'c'] ← 注意是列表不是字符串
sorted({3, 1, 2}) # [1, 2, 3]
sorted(d) # 对字典排序得到的是「键的列表」
sorted(d.items()) # 按 (键, 值) 元组排序
头号新手坑：
sort()返回None是故意的——这个返回值在提醒调用者：它是原地操作，没有新列表可拿。 记住：要新列表用sorted，要原地改用.sort()，两者不能混。
竞赛里的选择很简单：只要不需要保留原数组，就用 .sort()。
12.2 Timsort：稳定，且对部分有序数据极快¶
Python 的排序算法是 Timsort（归并排序 + 插入排序的混合体，由 Tim Peters 为 Python 发明， 后来被 Java、Android、V8 采用）。
| 性质 | 值 |
|---|---|
| 最坏 / 平均复杂度 | \(O(n \log n)\) |
| 最好复杂度 | \(O(n)\)（已经有序或接近有序时） |
| 空间 | \(O(n)\) |
| 稳定性 | 稳定 |
| 实现 | C 层（listsort.c），常数极小 |
两个直接的竞赛后果：
1. 不要自己写排序。 手写快排/归并是纯 Python 循环，比内建 sort 慢 50–100 倍。
\(n = 10^5\) 时内建 sort 约 0.03 秒，手写快排约 1.5 秒。
除非题目明确要求实现排序算法（见 40-排序），否则一律用内建。
2. 不用担心被卡。 手写的朴素快排可以被构造数据卡成 \(O(n^2)\)
（std::sort 有 introsort 兜底不会退化，但常数会明显变差）；
Timsort 的最坏情况就是 \(O(n \log n)\)，不存在「快排卡常数据」。
而且如果数据本来就接近有序，Timsort 快得离谱——这是很多题的隐藏加速点。
稳定性的含义¶
稳定 = 关键字相等的元素，排序后保持原来的相对先后顺序。
a = [("b", 1), ("a", 2), ("c", 1)]
sorted(a, key=lambda t: t[1])
# [('b', 1), ('c', 1), ('a', 2)]
# ↑ 'b' 原来在 'c' 前面，排完还在前面
稳定性是可以当算法用的，见 12.7。
12.3 key 函数：Python 排序的核心¶
key 是一个一元函数，排序前对每个元素调用一次，之后按返回值比较。
words = ["apple", "Bob", "cat"]
sorted(words, key=len) # 按长度
sorted(words, key=str.lower) # 忽略大小写
sorted(a, key=abs) # 按绝对值
sorted(pts, key=lambda p: p[0] ** 2 + p[1] ** 2) # 按到原点距离的平方
关键事实：key 恰好被调用 \(n\) 次¶
CPython 内部用的是装饰-排序-去装饰（decorate-sort-undecorate）流程：
先对每个元素算一次 key 存进数组，然后只比较这些 key 值，最后取回原元素。
| 方式 | key/cmp 调用次数 |
|---|---|
key=f |
恰好 \(n\) 次 |
| C++ 的比较函数 | \(O(n \log n)\) 次 |
cmp_to_key |
\(O(n \log n)\) 次 |
这条性质意味着key 里可以放昂贵的计算：
也意味着 key 函数不能有副作用、不能依赖调用顺序。
key 的返回值必须两两可比较¶
Python 3 取消了 Python 2 的「不同类型按类型名排序」的行为，
混合类型排序直接抛 TypeError。这在处理「有些字段缺失、用 None 填充」的数据时很容易撞上。
没有 key 时用什么比较？¶
元素自身的 < 运算符。对元组和列表是字典序逐元素比较：
这就是下一节「元组技巧」的全部原理。
12.4 多关键字排序：元组技巧¶
把关键字按优先级从左到右放进一个元组。 这是 Python 多关键字排序的标准做法。
元组比较是短路的：先比第 0 位，相等才比第 1 位，以此类推。
和 C++ 里写 if (a.score != b.score) return a.score > b.score; return a.id < b.id; 完全等价，但短得多。
优先级顺序错了是最常见的 WA。写之前先用中文说一遍： 「先按 X，X 相同再按 Y」，然后照着写
(X, Y)。
三个以上关键字同理¶
12.5 负号技巧与它的三个失效场景¶
要让某个数值关键字降序，最快的办法是取负：
它比 reverse=True 灵活，因为 reverse 是整体反转，没法只反转一部分。
负号技巧失效的三种情况：
| 失效场景 | 原因 | 对策 |
|---|---|---|
| 关键字是字符串 | -"abc" 是 TypeError |
两趟稳定排序（12.7）或 cmp_to_key |
| 关键字是元组 / 列表 | 不能取负 | 同上 |
关键字是浮点且含 nan |
nan 和谁比较都返回 False，排出来的顺序没有意义 |
先清洗数据 |
对于整数，还有一个不常用但有效的替代：如果值域已知且非负，可以用 MAX - x 代替 -x。
不过 Python 整数无上限，直接取负永远是最优解。
只有一个关键字且要降序时，
reverse=True比取负快（省掉一次lambda调用）：
12.6 reverse=True 与稳定性的交互¶
这是一个极易被误解的点：
a = [("b", 1), ("a", 1), ("c", 2)]
sorted(a, key=lambda t: t[1], reverse=True)
# [('c', 2), ('b', 1), ('a', 1)]
# ↑ 'b' 仍在 'a' 前面，相等元素的顺序 **没有** 被反转
reverse=True 不等于「排完再 reverse()」。
它只是把比较方向反过来，稳定性依然保持——相等元素维持原有相对顺序。
如果真的写成 sorted(a, key=...) 然后 .reverse()，相等元素的顺序会被翻转，
在有次关键字要求的题目里就是 WA。
| 写法 | 相等元素顺序 |
|---|---|
sorted(a, key=f, reverse=True) |
保持原顺序（稳定） |
sorted(a, key=f)[::-1] |
被反转 |
sorted(a, key=lambda x: -f(x)) |
保持原顺序（等价于第一种） |
竞赛里永远用 reverse=True 或负号，不要排完再反转。
12.7 稳定性当算法用：两趟排序¶
既然排序是稳定的，就可以从次要关键字到主要关键字，倒着排若干趟， 效果等价于一次多关键字排序。
# 目标：名字字典序【降序】，分数【升序】
# 名字是字符串，取不了负 → 负号技巧失效
a.sort(key=lambda t: t.name, reverse=True) # 第一趟：次关键字
a.sort(key=lambda t: t.score) # 第二趟：主关键字（稳定，保住第一趟的结果）
口诀：先排次要的，后排主要的。 顺序反了就全错。
这个技巧的价值在于：它能处理「混合升降序且某个字段不能取负」的情况，
而且比 cmp_to_key 快得多（两趟 C 层排序 vs 一趟带 Python 回调的排序）。
代价是要排 \(k\) 趟，复杂度 \(O(k \cdot n \log n)\)。\(k\) 通常只有 2–3，完全可以接受。
它也是基数排序（LSD radix sort）的原理，见 41-桶计数与离散化。
12.8 functools.cmp_to_key：什么时候不得不用¶
from functools import cmp_to_key
def cmp(x, y):
"""返回负数表示 x 排在 y 前，正数表示 y 排在 x 前，0 表示等价。"""
if x < y:
return -1
if x > y:
return 1
return 0
a.sort(key=cmp_to_key(cmp))
cmp_to_key 把 C++ 风格的二元比较函数包装成 Python 的一元 key：
它返回一个代理对象，对象的 __lt__ 里去调用传入的 cmp。
语义和 C++ 的
std::sort比较器不一样： C++ 的比较器返回bool（a是否严格小于b）， Python 的cmp返回int（负 / 零 / 正）。 从 C++ 直译过来常写成return x < y，结果True/False被当成1/0，排序结果错但不报错。
什么时候必须用它¶
只有一种情况：比较关系无法用「对每个元素单独算出的关键字」表达。
典型例子是拼接最大数：给若干数字串，拼成一个最大的数。
正确的比较规则是「a+b 和 b+a 哪个字典序大」——这是两个元素之间的关系，
没有任何单元素的 key 能表达它。
from functools import cmp_to_key
def cmp(x, y):
if x + y > y + x: # x 排前面能得到更大的拼接结果
return -1
if x + y < y + x:
return 1
return 0
parts = ["3", "30", "34", "5", "9"]
parts.sort(key=cmp_to_key(cmp))
print("".join(parts)) # 9534330
其它常见场景：田忌赛马式的比较、按自定义的次序关系——排序要求它是全序（任意两元素都可比，且比较可传递）；
只是偏序（允许存在互不可比的元素，如集合的包含关系）时，排序结果没有确定含义、
以及某些几何题里的极角比较（虽然极角通常可以用 atan2 当 key）。
什么时候不该用它¶
混合升降序不是理由。绝大多数「混合升降序」都能用元组 + 负号解决：
只有当降序字段是字符串或其它不能取负的类型时，才轮到候选方案。
即便这时，两趟稳定排序（12.7）也比 cmp_to_key 好：
# 名字降序、分数升序
a.sort(key=lambda t: t.name, reverse=True) # ✅ 首选：两趟稳定排序
a.sort(key=lambda t: t.score)
a.sort(key=cmp_to_key(my_cmp)) # ⚠️ 能用但慢约 5 倍，见下节实测
性能对照¶
对同一个 \(n = 10^5\) 的二元组列表实测（基准是不带 key 的 a.sort()，它比较的是整个元组）：
| 写法 | 耗时 | 相对基准 | 说明 |
|---|---|---|---|
a.sort() |
22 ms | 1.0× | 无 key，但每次要逐字段比较整个元组 |
a.sort(key=itemgetter(1)) |
13 ms | 0.6× | C 实现的 key；只比一个整数，反而更快 |
a.sort(key=lambda t: t[1]) |
15 ms | 0.7× | \(n\) 次 Python 调用，仍快于比整个元组 |
a.sort(key=lambda t: (-t[1], t[0])) |
32 ms | 1.5× | \(n\) 次调用 + 建元组，又变回比元组 |
a.sort(key=cmp_to_key(cmp)) |
109 ms | 5× | \(O(n \log n)\) 次 Python 调用 + 代理对象 |
前两行的方向可能与直觉相反：加了
key反而更快。 因为决定耗时的不是「有没有key」，而是每次比较有多贵——key只在排序前对每个元素算一次（\(n\) 次），比较却要做 \(O(n \log n)\) 次。 把一次性的取字段换掉反复进行的元组比较，是笔划算买卖。想单独看
key机制本身的开销，要让两边比同样的东西： 纯整数列表直接sort()是 11 ms，二元组列表sort(key=itemgetter(1))是 13 ms， 只贵了约 1.2 倍。所以key的固定成本很小， 真正要提防的是cmp_to_key——它把 Python 调用塞进了比较环节，次数从 \(n\) 涨到 \(O(n \log n)\)。
\(n = 10^5\)、时限 2 秒的题，cmp_to_key 通常还能过；\(n = 10^6\) 就危险了。
决策树： 1. 能用元组 + 负号吗？→ 用元组。 2. 不能（有字符串要降序）→ 用两趟稳定排序。 3. 比较规则根本不是「按某个值排」（如拼接最大数）→ 才用
cmp_to_key。
12.9 operator.itemgetter / attrgetter¶
operator 模块提供 C 实现的取值函数，用来替代最常见的那类 lambda：
from operator import itemgetter, attrgetter
a.sort(key=itemgetter(1)) # 等价 lambda t: t[1]，但快约 20%
a.sort(key=itemgetter(1, 0)) # 等价 lambda t: (t[1], t[0])
a.sort(key=attrgetter("score")) # 等价 lambda o: o.score
a.sort(key=attrgetter("pos.x")) # 支持点号链式取属性
d_sorted = sorted(d.items(), key=itemgetter(1)) # 按字典的值排序
itemgetter 也能用于字典键：
| 需求 | 推荐写法 |
|---|---|
| 取单个下标/属性 | itemgetter(i) / attrgetter("name") |
| 取多个下标做元组（全部升序） | itemgetter(1, 0) |
| 升降序混合 | itemgetter 做不到，改用 lambda t: (-t[1], t[0]) |
需要计算（如 -t[1]、abs(x)） |
lambda，或直接传内建函数如 key=abs |
itemgetter只能取，不能算。要取负就只能回到lambda。 好在最常见的「元素本身就是元组、且全部升序」的情况， 连key都不用写——直接a.sort()是最快的。
operator 模块的其它常用成员（配合 reduce 用）：
from operator import add, mul, xor, and_, or_
from functools import reduce
reduce(xor, a, 0) # 全体异或
reduce(mul, a, 1) # 全体乘积
12.10 自定义类的 __lt__¶
如果同一个类在多处都按同一规则排序，与其到处写 key，不如给类定义比较运算符。
Python 排序只需要 __lt__（小于），不需要实现全部六个比较运算符：
class Student:
__slots__ = ("sid", "score") # 省内存 + 提速，属性固定时值得写
def __init__(self, sid, score):
self.sid = sid
self.score = score
def __lt__(self, other):
# 分数降序，分数相同学号升序
if self.score != other.score:
return self.score > other.score
return self.sid < other.sid
def __repr__(self): # 方便调试时直接 print
return "Student(%d, %d)" % (self.sid, self.score)
a = [Student(3, 90), Student(1, 95), Student(2, 90)]
a.sort() # 直接排，不需要 key
__lt__ 的另一个重要用途是 heapq——堆内部只用 < 比较：
不定义 __lt__ 而往堆里塞元组 (score, sid, obj) 时，一旦前两项相等，
Python 会去比较 obj，此时如果 obj 没有 __lt__ 就会 TypeError。
这是堆题最隐蔽的 RE 来源，详见 35-优先队列与堆。
常用比较相关魔术方法¶
| 方法 | 触发 | 排序/堆是否需要 |
|---|---|---|
__lt__(self, other) |
a < b |
需要（sort、heapq 只用它） |
__eq__ |
a == b |
不需要排序，但做 dict 键时需要 |
__hash__ |
hash(a) |
做 dict 键 / set 元素时需要 |
__gt__ / __le__ / __ge__ |
对应运算符 | 一般不需要 |
__repr__ |
print / 调试 |
强烈建议写 |
想一次补齐六个运算符，用 functools.total_ordering 装饰类（只需再提供 __eq__）。
竞赛里通常不必——只写 __lt__ 就够了。
竞赛权衡：自定义类比元组慢。\(n = 10^5\) 以下随便用； \(n \ge 10^6\) 时用元组（
(-score, sid)）或并行数组，能省一半时间和大量内存。
12.11 排序相关的其它函数¶
max(a, key=f) # 按 key 取最大元素本身（不是 key 值）
min(a, key=len)
sorted(a, key=f)[:k] # 取前 k 小，O(n log n)；k 与 n 同量级时用它
import heapq
heapq.nsmallest(k, a, key=f) # ✅ 取前 k 小，O(n log k)，k 远小于 n 时快得多
heapq.nlargest(k, a, key=f)
import bisect
bisect.insort(a, x) # 保持有序地插入，查找 O(log n) 但插入 O(n)
heapq.nsmallest(k, a)在 \(k\) 接近 \(n\) 时反而比sorted(a)[:k]慢。 经验阈值：\(k < n / 10\) 用nsmallest，否则直接排序。
12.12 例题¶
BISHI21 【模板】排序（入门）¶
给长度 \(n\ (1 \le n \le 10^5)\) 的整数数组（\(-10^9 \le a_i \le 10^9\)）， 按非递减顺序排序并在一行输出。 题面见 BISHI21 原题（牛客）。
模板题，但它验证了本章最重要的一句话：不要自己写排序。
import sys
def main():
data = sys.stdin.buffer.read().split()
a = list(map(int, data[1:])) # data[0] 是 n，用不上
a.sort()
sys.stdout.write(" ".join(map(str, a)) + "\n")
main()
四个要点：
a.sort()而不是a = sorted(a)：原地排序省一次 \(O(n)\) 的列表构造。data[1:]直接切掉n：token 流思维，n不参与计算。- 输出用
" ".join，不要print(*a)。\(10^5\) 个元素时join明显更快 （print(*a)内部要逐个格式化并处理sep）。 - 有负数，所以不能用计数排序偷懒（值域 \(2 \times 10^9\)）。Timsort 的 \(O(n \log n)\) 完全够。
如果这题手写快排会怎样？\(n = 10^5\) 时纯 Python 快排约 1.5 秒 + 递归深度风险， 而
a.sort()只要 0.02 秒。差 70 倍。
BISHI22 分数线划定（简单，多关键字排序）¶
\(n\) 名选手（\(5 \le n \le 5000\)），每人有报名号 \(k\) 和成绩 \(s\)。 按成绩降序、成绩相同报名号升序排序，取 \(t = \lfloor 1.5m \rfloor\) 名选手的成绩作为分数线， 输出分数线和实际进入面试的人数，再按排序顺序输出这些选手。 题面见 BISHI22 原题（牛客）。
这是元组技巧 + 负号技巧的教科书例题：
import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [(int(data[2 + 2 * i]), int(data[3 + 2 * i])) for i in range(n)] # (报名号, 成绩)
a.sort(key=lambda t: (-t[1], t[0])) # 成绩降序，报名号升序
t = m * 3 // 2 # ⌊1.5m⌋，用整数运算避免浮点
line = a[t - 1][1] # 第 t 名的成绩（下标从 0 开始，所以是 t-1）
ok = [p for p in a if p[1] >= line] # 所有不低于分数线的人
out = ["%d %d" % (line, len(ok))]
out.extend("%d %d" % p for p in ok)
sys.stdout.write("\n".join(out) + "\n")
main()
五个关键点：
(-t[1], t[0])：成绩要降序所以取负，报名号要升序所以原样。 两个关键字的类型都是int，负号技巧完全适用。m * 3 // 2而不是int(m * 1.5)。\(1.5m\) 用浮点算， \(m\) 稍大时可能出现4.499999999被截断成 4 的情况。 整数除法能做的事，永远别交给浮点。t - 1：题目说「第 \(t\) 名」是 1-indexed，Python 列表是 0-indexed。 这类差一错误是本题的主要失分点。ok用列表推导过滤，而不是再排一次或二分——\(n \le 5000\)，\(O(n)\) 扫一遍最省事。 由于已按成绩降序排好，ok其实就是a的一个前缀，也可以用bisect求边界，但没必要。- 输出人数 \(cnt \ge t\)，因为可能有多人并列压线。直接输出
len(ok)，不要输出t。
BISHI23 小红书推荐系统（简单，哈希 + 排序）¶
给一行由小写字母和空格组成的字符串（长度 \(\le 10^5\)）， 统计每个单词出现次数，输出所有出现不少于 3 次的单词， 按频次从高到低排序，频次相同按字典序升序。 题面见 BISHI23 原题（牛客）。
「频次降序 + 字典序升序」——升降混合，但降序的那个是数字，所以负号技巧依然适用：
import sys
from collections import Counter
def main():
words = sys.stdin.read().split() # split() 自动处理连续空格
cnt = Counter(words)
keys = [w for w, c in cnt.items() if c >= 3]
keys.sort(key=lambda w: (-cnt[w], w)) # 频次降序，字典序升序
sys.stdout.write("\n".join(keys) + "\n")
main()
要点：
Counter一行完成计数，见 14-标准库速查。 手写defaultdict(int)循环也行，但Counter(list)是 C 层实现，快得多。(-cnt[w], w)：第一项是int可以取负，第二项是str保持升序—— 这正是负号技巧的适用边界。如果题目要求「字典序降序」，负号就用不了了， 此时的解法是两趟稳定排序：先keys.sort(reverse=True)，再keys.sort(key=lambda w: -cnt[w])。key里查了字典cnt[w]。因为key只被调用 \(n\) 次，这个查找的总开销是 \(O(n)\)， 完全可以接受。换成cmp_to_key就会变成 \(O(n \log n)\) 次字典查找。- 也可以用
cnt.most_common()，但它只保证按频次降序，不保证同频次的字典序， 所以还是得再排一次。直接自己排更清晰。
BISHI24 谐距下标对（入门，排序 / 计数）¶
长度 \(n\ (1 \le n \le 10^5)\) 的数组，求满足 \(i < j\) 且 \(a_j - a_i = j - i\) 的下标对数量。 题面见 BISHI24 原题（牛客）。
移项是这题的全部：
于是问题变成「有多少对下标的 \(a_i - i\) 相同」。每组大小为 \(c\) 的相同值贡献 \(\binom{c}{2}\) 对。
import sys
from collections import Counter
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
# data[0] 是 n，所以第 i 个元素在 data[1 + i]，这个 1 是跳过 n 的偏移量；
# 减 i 就是移项后的 a_i - i，值相同的下标两两配对即为一组答案
cnt = Counter(int(data[1 + i]) - i for i in range(n))
# 同一个值出现 c 次就贡献 C(c,2) = c*(c-1)/2 对；
# 用整除 // 而不是 /，避免大数转成浮点后丢精度
print(sum(c * (c - 1) // 2 for c in cnt.values()))
main()
这题放在排序章，是因为它示范了排序思维的两个层次：
- 能做：把 \(b_i = a_i - i\) 排序，然后扫一遍数相同值的连续段。\(O(n \log n)\)。
- 更好：根本不需要顺序，只需要「每个值出现几次」，用
Counter就是 \(O(n)\)。
# 排序版（也能过，但没必要）
b = sorted(a[i] - i for i in range(n))
ans = i = 0
while i < n:
j = i
while j < n and b[j] == b[i]:
j += 1
c = j - i
ans += c * (c - 1) // 2
i = j
判断口诀：需要「顺序」才排序，只需要「分组」就用字典。 很多题目看到「统计满足某关系的对数」就条件反射排序，其实哈希计数更快也更短。
注意 \(a_i - i\) 可能是负数（\(a_i \ge 1\) 而 \(i\) 最大到 \(n-1\)），
用 Counter 完全没问题，用数组下标就得先偏移。这是哈希优于桶的又一个理由。
BISHI25 最大 FST 距离（中等，排序 / 曼哈顿距离变换）¶
给 \(n\ (1 \le n \le 10^5)\) 个数 \(A_i\)，定义 \(\mathrm{dist}(i,j) = |i^2 - j^2| + |A_i^2 - A_j^2|\)（下标 \(i\) 从 1 开始）， 求所有元素对中的最大值。 题面见 BISHI25 原题（牛客）。
暴力枚举是 \(O(n^2) = 10^{10}\)，必然 TLE。
令 \(u_i = i^2\)、\(v_i = A_i^2\)，问题就是求平面上 \(n\) 个点两两之间的最大曼哈顿距离。 关键恒等式：
因为绝对值可以拆成 \(\pm\) 两种情况，四种符号组合归并后就剩 \(u+v\) 和 \(u-v\) 两个投影。 于是答案 = 两个投影各自的极差中的较大者：
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
p = [] # 第一个投影方向 u + v
q = [] # 第二个投影方向 u - v
# 题目的下标 i 从 1 数起，而 data[0] 是 n、元素从 data[1] 开始，
# 两边正好对齐：循环变量 i 既是题目下标，又是 data 的下标，不需要再偏移
for i in range(1, n + 1):
u = i * i
v = int(data[i]) ** 2
p.append(u + v)
q.append(u - v)
# 每个方向上「最远的一对」必是该方向的最大值与最小值，所以取极差即可；
# 两个方向的极差取较大者，就是最大曼哈顿距离
print(max(max(p) - min(p), max(q) - min(q)))
main()
这题被归到排序章，是因为它回答了一个反复出现的问题：排序到底在解决什么。
- 朴素思路「按 \(A_i\) 排序后只看首尾」是错的——距离同时依赖下标 \(i\) 和值 \(A_i\)， 按 \(A_i\) 排序会破坏 \(i\) 的信息。
- 正确思路是换坐标：变换到 \(u \pm v\) 两个方向后， 每个方向上「最远的一对」就是「最大值和最小值」。
- 而找最值根本不需要排序——
max/min是 \(O(n)\)，排序是 \(O(n \log n)\)。
教训：排序的用途是「让某种顺序变得可利用」。 只要极值就用
max/min；只要分组，用Counter； 只要第 \(k\) 大，用heapq.nsmallest。排序是手段不是目的。另外注意 \(A_i \le 10^9\)，所以 \(A_i^2 \le 10^{18}\)，\(u + v\) 可到约 \(10^{18}\)。 C++ 必须开
long long并小心中间溢出，Python 的int无上限，完全不用管。
同类变换见 110-计算几何入门 的切比雪夫距离一节。
BISHI12 元素方碑（中等，不变量）¶
\(n\) 块方碑能量为 \(a_i\)。可对 \(2 \le i \le n-1\) 的方碑操作： 使 \(a_{i-1}\) 减 1、\(a_{i+1}\) 加 1（或反向），过程中所有 \(a_i\) 必须非负。 问能否让所有方碑能量相等。多组数据，\(\sum n \le 2 \times 10^5\)。 题面见 BISHI12 原题（牛客）。
这题的正解和排序毫无关系，把它放在本章末尾，是为了给「排序万能论」踩一脚刹车。
观察操作：能量只在 \(i-1\) 和 \(i+1\) 之间移动，这两个下标的奇偶性相同。 所以「奇数位的能量总和」和「偶数位的能量总和」都是不变量。
设目标值 \(\text{avg} = \sum a_i / n\)，奇数位有 \(c_{\text{odd}}\) 个、偶数位有 \(c_{\text{even}}\) 个，则答案为 YES 当且仅当：
- \(\sum a_i\) 能被 \(n\) 整除；
- 奇数位之和 \(= \text{avg} \times c_{\text{odd}}\)（偶数位由总和自动满足）。
（非负约束不会成为障碍：同一奇偶类里的能量可以逐格搬运，初始 \(a_i \ge 1\) 保证搬得动。）
import sys
def main():
data = sys.stdin.buffer.read().split()
p = 0
t = int(data[p]); p += 1
out = []
for _ in range(t):
n = int(data[p]); p += 1
a = list(map(int, data[p:p + n])); p += n
s = sum(a)
if s % n:
out.append("NO")
continue
avg = s // n
odd = sum(a[0::2]) # 1-indexed 的奇数位 = 0-indexed 的偶数下标
if odd == avg * len(a[0::2]):
out.append("YES")
else:
out.append("NO")
sys.stdout.write("\n".join(out) + "\n")
main()
要点：
- 排序会直接毁掉这题。答案依赖每个元素所在位置的奇偶性， 一旦排序，位置信息全部丢失。凡是题目里「下标」参与运算的，排序前先想清楚。
a[0::2]是切片取偶数下标，对应 1-indexed 的奇数位。切片在 C 层完成，比循环快。 真要抠常数可以写sum(a[0::2])与(n + 1) // 2直接算个数，避免建第二个切片。s % n先判整除，避免后面出现浮点。用s / n会引入浮点误差，\(a_i \le 10^9\)、 \(n \le 2\times10^5\) 时 \(\sum a_i\) 可达 \(2 \times 10^{14}\)，float只有 15–17 位有效数字， 相当危险。能整除判断就别做除法。- 多组数据 + \(\sum n \le 2\times10^5\)，用 token 流游标读入，见 20-输入输出处理。
本章最后一条经验：拿到题先问「排序之后，我还需不需要原来的下标？」 需要的话，要么排
(值, 下标)的元组把下标带上，要么根本别排。
完整题解：BISHI21、BISHI22、BISHI23、BISHI24、BISHI25、BISHI12
12.13 本章速查¶
| 需求 | 写法 |
|---|---|
| 原地排序 | a.sort()，返回 None，别写 a = a.sort() |
| 返回新列表 | sorted(x)，接受任意可迭代对象 |
| 算法 | Timsort，\(O(n\log n)\)，稳定，接近有序时 \(O(n)\) |
| 手写排序 | 别写，比内建慢 50–100 倍 |
| 单关键字 | key=len / key=abs / key=itemgetter(1) |
| 多关键字全升序 | key=itemgetter(1, 0) 或元素本身是元组时直接 a.sort() |
| 数值降序 + 其它升序 | key=lambda t: (-t[1], t[0]) |
| 整体降序 | reverse=True（比 key=lambda x: -x 快） |
| 字符串降序 + 其它升序 | 两趟稳定排序：先排次关键字（reverse=True），再排主关键字 |
| 排完再反转 | 绝不要，会破坏相等元素的相对顺序 |
reverse=True |
仍然稳定，不等于 [::-1] |
key 调用次数 |
恰好 \(n\) 次，所以 key 里可以做昂贵计算 |
cmp_to_key |
只在「比较规则不能表示成单元素 key」时用（如拼接最大数），实测慢约 5 倍 |
cmp 返回值 |
负 / 0 / 正的 int，不是 bool |
| 自定义类排序 | 只需实现 __lt__；heapq 也只用 __lt__ |
| 前 \(k\) 小 | \(k < n/10\) 用 heapq.nsmallest(k, a)，否则 sorted(a)[:k] |
| 按 key 取最值 | max(a, key=f) 返回元素不是 key 值 |
| 混合类型 | Python 3 直接 TypeError |
| 需要原下标 | 排 (值, 下标) 元组，或干脆别排 |
| 只要分组 | 用 Counter，\(O(n)\) 优于排序 |
| 只要极值 | 用 max/min，\(O(n)\) 优于排序 |