第 12 章 自定义排序¶
本章配套 6 道例题，见 §例题。
排序是笔试题里出现频率最高的操作，没有之一。而 Python 的排序和 C++ 的
std::sort 思路完全不同：C++ 给的是「比较函数」，Python 给的是「关键字函数」。
这个差异不是语法糖，而是性能量级的差别——用错了会从 \(O(n \log n)\) 次比较
退化成 \(O(n \log n)\) 次 Python 函数调用。本章是第一部分的重点章，会把
key、稳定性、cmp_to_key 三件事讲透。
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()。
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 秒。
除非题目明确要求实现排序算法（见 排序），否则一律用内建。
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' 前面，排完还在前面
稳定性是可以当算法用的，见 §7。
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 时用什么比较？¶
元素自身的 < 运算符。对元组和列表是字典序逐元素比较：
这就是下一节「元组技巧」的全部原理。
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)。
三个以上关键字同理¶
5 负号技巧与它的三个失效场景¶
要让某个数值关键字降序，最快的办法是取负：
它比 reverse=True 灵活，因为 reverse 是整体反转，没法只反转一部分。
负号技巧失效的三种情况：
| 失效场景 | 原因 | 对策 |
|---|---|---|
| 关键字是字符串 | -"abc" 是 TypeError |
两趟稳定排序（§7）或 cmp_to_key |
| 关键字是元组 / 列表 | 不能取负 | 同上 |
关键字是浮点且含 nan |
nan 和谁比较都返回 False，排出来的顺序没有意义 |
先清洗数据 |
对于整数，还有一个不常用但有效的替代：如果值域已知且非负，可以用 MAX - x 代替 -x。
不过 Python 整数无上限，直接取负永远是最优解。
只有一个关键字且要降序时，
reverse=True比取负快（省掉一次lambda调用）：
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 或负号，不要排完再反转。
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）的原理，见 桶计数与离散化。
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）。
什么时候不该用它¶
混合升降序不是理由。绝大多数「混合升降序」都能用元组 + 负号解决：
只有当降序字段是字符串或其它不能取负的类型时，才轮到候选方案。
即便这时，两趟稳定排序（§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。
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) # 全体乘积
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 来源，详见 优先队列与堆。
常用比较相关魔术方法¶
| 方法 | 触发 | 排序/堆是否需要 |
|---|---|---|
__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)）或并行数组，能省一半时间和大量内存。
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 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI21 | 【模板】排序 | 入门 | 题解 |
| BISHI22 | 分数线划定 | 简单 | 题解 |
| BISHI23 | 小红书推荐系统 | 简单 | 题解 |
| BISHI24 | 谐距下标对 | 入门 | 题解 |
| BISHI25 | 最大 FST 距离 | 中等 | 题解 |
| BISHI12 | 元素方碑 | 中等 | 题解 |
BISHI21 【模板】排序（入门）¶
给长度 \(n\ (1 \le n \le 10^5)\) 的整数数组（\(-10^9 \le a_i \le 10^9\)）， 按非递减顺序排序并在一行输出。 题面见 原题。
模板题，但它验证了本章最重要的一句话：不要自己写排序。
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\) 名选手的成绩作为分数线， 输出分数线和实际进入面试的人数，再按排序顺序输出这些选手。 题面见 原题。
这是元组技巧 + 负号技巧的教科书例题：
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) # p 是二元组，正好填满两个占位符
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。 "%d %d" % p里的p直接就是元组。%格式化要求右边是元组，多个占位符 就按位置一一对应；这里p恰好是(报名号, 成绩)，不用再拆成% (p[0], p[1])。 反过来，只有一个占位符时传元组是这个语法最常见的坑，见 字符串。
BISHI23 小红书推荐系统（简单，哈希 + 排序）¶
给一行由小写字母和空格组成的字符串（长度 \(\le 10^5\)）， 统计每个单词出现次数，输出所有出现不少于 3 次的单词， 按频次从高到低排序，频次相同按字典序升序。 题面见 原题。
「频次降序 + 字典序升序」——升降混合，但降序的那个是数字，所以负号技巧依然适用：
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一行完成计数，见 标准库速查。 手写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\) 的下标对数量。 题面见 原题。
移项是这题的全部：
于是问题变成「有多少对下标的 \(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 开始）， 求所有元素对中的最大值。 题面见 原题。
暴力枚举是 \(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无上限，完全不用管。
这个换坐标的手法在计算几何里叫曼哈顿距离与切比雪夫距离的互化， 上面三条已经把它用到的部分讲完了；想看它在几何题里的样子， 可以带着这个印象读 计算几何入门。
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\)。 题面见 原题。
这题的正解和排序毫无关系，把它放在本章末尾，是为了给「排序万能论」踩一脚刹车。
观察操作：能量只在 \(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 流游标读入，见 输入输出处理。
本章最后一条经验：拿到题先问「排序之后，还需不需要原来的下标？」 需要的话，要么排
(值, 下标)的元组把下标带上，要么根本别排。
完整题解：【模板】排序、分数线划定、小红书推荐系统、谐距下标对、最大 FST 距离、元素方碑
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)\) 优于排序 |