环形均分纸牌与中位数贪心：从七夕祭到通用解法

做这道题之前，我一直觉得“环形均分纸牌”和“中位数贪心”是两套互不相干的知识点：一个负责模拟搬运过程，一个负责在数轴上找最优位置。直到完整刷完 P10453 七夕祭，我才意识到这两个东西其实是一体两面——前者给出问题模型，后者给出数学答案。这篇文章我把自己的推导过程和踩坑记录都放出来，希望帮你一次性吃透这个组合套路。

如果你正在备战 CSP/NOIP，或者刚开始刷洛谷的经典题，P10453 是一个非常好的观测样本。它表面上是二维网格上的复杂交换问题，但抽掉外壳后发现，核心不过是一维环形均分纸牌，而且行方向和列方向完全独立。理解了这个，你不仅会做这一道题，还会顺带掌握一大类“把环切开成链”的贪心证明方法。

1. 题目本质拆解：看似二维，实则是两条独立的环形均分纸牌

1.1 先看懂交换操作到底在干什么

七夕祭的题面给了一个 n 行 m 列的网格，里面有一些特殊摊位。你只能做一种操作：交换相邻两个格子里的东西。相邻包括上下相邻和左右相邻，每次交换代价为 1。

我一开始想复杂了，以为这是在网格上做二维匹配。实际上你盯住某个特殊摊位看，交换相邻格子，本质就是让这个特殊摊位在网格上往上下左右移动一格。如果一个格子是空的，那一次交换就等价于特殊摊位瞬移一步；即使两个格子都有特殊摊位，交换也只是让两个特殊摊位同时向对方方向各移动一步，总代价依然可以按每个特殊摊位走过的路径长度来理解。

这个视角非常关键。因为它把操作从“抽象的格子交换”翻译成了“棋子在网格上移动”，后面才能把行、列分开看。

1.2 行和列为什么能拆开算

现在考虑两类操作：

• 上下交换：改变特殊摊位所在的行，但不改变它所在的列。
• 左右交换：改变特殊摊位所在的列，但不改变它所在的行。

这意味着，如果你想调整第 i 行和第 i+1 行的特殊摊位数量，只能用上下交换，左右交换完全帮不上忙。同理，调整第 j 列和第 j+1 列的数量，只能用左右交换。

所以一个 n×m 的二维问题，直接退化成了两个一维问题：行方向上的均分纸牌，和列方向上的均分纸牌。两者用的操作不同，互相不干扰，最终答案就是两个一维答案相加。

这里要注意一个细节：有人会问，我先做左右交换，再做上下交换，会不会导致前面白做了？不会。因为上下交换不改变每行的总数，左右交换不改变每列的总数，两个维度的进度可以被同时推进。就像你同时整理书架的两层，虽然每次只能动一本书，但整理上层和整理下层是完全独立的两件事。

1.3 可行性判定：整除条件优先于一切

在算最小步数之前，必须先回答“能不能做到”。

• 要让每一行特殊摊位数量相等，必须满足总摊位数量 t 能被行数 n 整除。
• 要让每一列特殊摊位数量相等，必须满足总摊位数量 t 能被列数 m 整除。

于是分成四种情况：

这个判定必须在调用核心函数之前做。我见过有同学在 t % n != 0 的时候还硬去算前缀和，其实也能得到一个“数值结果”，但这个结果毫无物理意义，因为它对应的平均数是小数，不可能通过整数次交换达成。

2. 数学模型：从线性均分到环形均分

2.1 线性版本的经典结论：前缀和就是边界流量

先复习线性均分纸牌问题。假设有一排 n 堆纸牌，a[i] 表示第 i 堆数量，目标是让每堆都变成平均数 avg。一次操作可以把一堆中的若干张牌移动到相邻堆，代价是移动的张数。

定义差值 b[i] = a[i] - avg，正数表示这堆多出来了，负数表示这堆还缺。

再定义前缀和 s[i] = b[1] + b[2] + ... + b[i]。s[i] 的含义非常直观：前 i 堆整体是多了还是少了。如果 s[i] > 0，说明前 i 堆多出来的牌必须越过第 i 和第 i+1 堆之间的边界，向右传递；如果 s[i] < 0，说明前 i 堆缺少的牌必须从右边越过边界补进来。总之，第 i 和第 i+1 堆之间最少要移动的牌数就是 |s[i]|。

所以线性答案等于：

ans = |s[1]| + |s[2]| + ... + |s[n-1]|

最后一项不用加，因为 s[n] 一定是 0。这个公式我用小数据验证过，比如 a = [9, 8, 17]，平均数是 11，差值 b = [-2, -3, 6]，前缀和 s = [-2, -5, 0]，答案就是 2 + 5 = 7。实际模拟：从第三堆移动 5 张到第二堆，再从第二堆移动 2 张到第一堆，总共 7 次，完美吻合。

2.2 环形版本多出来的自由度：切断点怎么选

P10453 的核心不是线性模型，而是环形模型。因为网格的行与行之间、列与列之间都是首尾相连的：第 n 行和第 1 行相邻，第 m 列和第 1 列相邻。

环形和线性最大的区别在于：线性的“边界”是固定的，而环形可以任意挑选一条边把它切断，变成线性问题。而且选择不同的切断位置，答案不同。

引入一个变量 c，代表把环切断后，跨过切口那条边的净流量。你可以把 c 理解为“从第 n 堆绕回第 1 堆的牌数”。一旦确定了 c，每条边的流量就都确定了。

具体来说，设 s[i] 是从某个固定起点开始计算的前缀和，那么切断后第 i 条边的流量可以统一写成 s[i] - c。总代价变成：

ans(c) = |s[1] - c| + |s[2] - c| + ... + |s[n] - c|

注意这次加到了第 n 项，因为 s[n] 对应的正好是切口那一条边。

于是问题变成了：找一个最优的 c，让这 n 个绝对值之和最小。

2.3 中位数为什么是最优解：一个凸函数的直觉

现在纯粹的数学问题出现了。有 n 个数 s[1], s[2], ..., s[n]，求一个实数 c，让 f(c) = Σ|s[i] - c| 最小。

这个函数是凸函数，而且分成 n 段线性。它的斜率变化很有意思：

• 当 c 很小，所有 s[i] 都在 c 右边，f(c) 的斜率是 -n。
• 随着 c 不断右移，每经过一个 s[i]，就有一个绝对值从“递减”变成“递增”，斜率增加 2。
• 当 c 过了中位数之后，右边的数多于左边的数，斜率变成正数，继续右移只会让 f(c) 变大。

所以最优位置一定落在“左边数字个数等于右边数字个数”的地方，也就是中位数位置。你可以这样记忆：绝对值函数的最优解，是中位数；平方和函数的最优解，才是平均数。

回到代码实现，排序之后取第 n/2 个或者第 (n+1)/2 个元素都行，因为偶数个时中间两个数之间的整个区间都是最优解。

2.4 把公式落到代码端：前缀和中位数法

环形均分纸牌的完整算法流程就非常清晰了：

1. 计算平均数 avg。
2. 对 i 从 1 到 n，计算 s[i] = s[i-1] + a[i] - avg。
3. 把 s[1] 到 s[n] 这 n 个值排序。
4. 取中位数 mid。
5. 答案 = Σ|s[i] - mid|。

为什么要包含 s[n]？因为环形的切口边被抽象成了 s[n] 对应的那条边，而 s[n] 其实等于 0，因为所有差值加起来的和一定是 0。这个 0 是有实际意义的，它代表了“如果选择在某个位置切断，切口处可以没有流量经过”这种可能性。漏掉它，在某些数据上会差出一个很大的常数。

3. 完整实现：P10453 七夕祭的 C++ 解法

3.1 数据模型：行数组和列数组分别计数

读入特殊摊位坐标，用两个计数数组分别记录每行的特殊摊位数量和每列的特殊摊位数量。

int n, m, t; cin >> n >> m >> t; vector<int> rowCnt(n + 1, 0), colCnt(m + 1, 0); for (int i = 0; i < t; i++) { int x, y; cin >> x >> y; rowCnt[x]++; colCnt[y]++; }

这里行数和列数都从 1 开始编号，所以数组开 n+1 和 m+1 的大小。不要混用，行数组的大小是 n+1，列数组的大小是 m+1，一旦搞反，越界访问在本地可能不明显，在 OJ 上就会随机 RE 或者 WA。

3.2 核心函数：环形均分纸牌的板子

直接封装一个函数，传入一维计数数组和它的长度，返回最小操作次数。如果余数不为 0，返回 -1 表示不可行。

long long ringDivide(vector<int>& cnt, int len, int total) { if (total % len != 0) { return -1; } int avg = total / len; vector<long long> s(len + 1, 0); for (int i = 1; i <= len; i++) { s[i] = s[i - 1] + cnt[i] - avg; } vector<long long> vals; vals.reserve(len); for (int i = 1; i <= len; i++) { vals.push_back(s[i]); } sort(vals.begin(), vals.end()); long long mid = vals[len / 2]; long long ans = 0; for (int i = 1; i <= len; i++) { ans += llabs(s[i] - mid); } return ans; }

有几个实现细节想强调：

• 为什么用 long long？前缀和可能达到 1e5 级别，加总后可能到 1e10，int 必爆。
• 为什么排序后取 len/2 而不是 (len+1)/2？对于偶数个数，两个中位数都合法，取下标 len/2 是“上中位数”，也完全正确。
• 为什么不直接把 s 数组 slice 出来？因为 vector 切片要么复制要么用迭代器，这里为了教学清晰，我显式 push 了一份。

如果想更快，可以用 nth_element 把排序优化成线性复杂度，代码改成：

nth_element(vals.begin(), vals.begin() + vals.size() / 2, vals.end()); long long mid = vals[vals.size() / 2];

nth_element 之后，下标 mid 位置的元素已经是“全局第 mid 小的元素”，不需要完整有序。竞赛环境下性能差距不大，但这个是很好的习惯。

3.3 主逻辑：四种输出情况

主函数里按整除情况分类调用：

bool okRow = (t % n == 0); bool okCol = (t % m == 0); if (!okRow && !okCol) { cout << "impossible\n"; } else if (okRow && okCol) { long long a = ringDivide(rowCnt, n, t); long long b = ringDivide(colCnt, m, t); cout << "both " << a + b << '\n'; } else if (okRow) { long long a = ringDivide(rowCnt, n, t); cout << "row " << a << '\n'; } else { long long b = ringDivide(colCnt, m, t); cout << "column " << b << '\n'; }

这里有个常见的误区：当 okRow 为真、okCol 为假时，有人会把 colCnt 也扔给 row 的调用函数，试图同时算两个答案。千万别这样，rowCnt 和 colCnt 长度可能不相等，算法内部的平均值、前缀和都会被污染。

3.4 手算验证一个完整样例

我构造一个例子：n=3, m=3, t=3，三个特殊摊位在 (1,2), (2,2), (3,3)。

行计数数组：

rowCnt[1]=1, rowCnt[2]=1, rowCnt[3]=1

t%n=0，平均数是 1。计算前缀和：s[1]=0, s[2]=0, s[3]=0，排序后中位数是 0，行方向答案 0。没错，每行本来就已经各有一个，不需要操作。

列计数数组：

colCnt[1]=0, colCnt[2]=2, colCnt[3]=1

t%m=0，平均数也是 1。差值序列是 -1, 1, 0，前缀和 s[1]=-1, s[2]=0, s[3]=0？等一下，这里要算清楚：

• s[1] = 0 - 1 = -1
• s[2] = s[1] + 2 - 1 = 0
• s[3] = s[2] + 1 - 1 = 0

排序后 vals = [-1, 0, 0]，中位数取 len/2 = 1，也就是 0。绝对值之和 = | -1 - 0 | + |0 - 0| + |0 - 0| = 1。

所以列方向答案是 1，整体输出 both 1。实际验证：第一列少 1 个，第二列多 1 个，把 (2,2) 位置的摊位左移一步到 (2,1)，列数量变成 1,1,1，每行数量本来就没变，完美达成目标。这个例子直观展示了公式计算的正确性。

4. 实战复盘：我踩过的几个坑

4.1 中位数取错位置，偶数数据翻车

我第一次实现时用的是 s[(len+1)/2] 作为中位数，那是在某种线性公式里常用的写法。但环形版本我用的是包含 s[len] 的一组前缀和，元素个数是 len。当 len 为偶数时，s[(len+1)/2] 取的是偏左的位置，而 s[len/2] 取的是偏右的位置，两者都能得到最优值。问题不在这。

真正的问题是：如果你在构造 vals 时不小心漏掉了 s[len] 这一项，只 push 了 s[1] 到 s[len-1]，那么元素个数变成 len-1，中位数的“第 k 小”语义就全变了。尤其在 len 为偶数时，漏一个数可能会导致答案差出好几倍。我建议每次写完都用一个 len=2 或 len=4 的小样例手推验证。

4.2 整除判定放错了顺序

有同学先算出平均数 avg = t / n，然后再判断 t % n 是否为 0。这个顺序在 C++ 里很危险，因为整数除法直接截断小数，后续的前缀和计算基于一个假的平均数值，整个差值体系都是错的。正确做法是先判断余数，再计算平均数。

我在本地测试时用过 t=7, n=3 的数据，如果真的先除后判，平均数是 2，差值前缀和算出来一个看似合理的结果，但在 OJ 上必然 WA。这种错误非常隐蔽，因为它不会报溢出或者越界，只是结果不对。

4.3 前缀和数组需要单独开 long long

计数数组本身是 int 没问题，因为每个位置最多 t 个，t 一般不超过 1e5。但前缀和一旦累加就可能超出 int 范围。举一个极端例子：如果 t=1e5，n=1，所有差值都集中在同一项，观察 s 序列从 0 到接近 1e5，虽然单个前缀和看起来不大，但多个差值的绝对值累加之后，最终答案可能到 1e10 级别。

我在第一版代码里为了省内存，直接 int ans，结果样例过了，提交后大数据直接爆掉。后来把所有跟前缀和、累加相关的变量都改成 long long，才真正稳定。

4.4 行、列数组混用导致的神秘错误

这个坑说大不大，但特别容易发生在考场紧张的时候：读入坐标后，不小心把 x 加到了 colCnt，把 y 加到了 rowCnt。因为输入格式是 x 代表行、y 代表列，一旦写反，前面的整除条件还可能恰好成立，但答案怎么都不对。

我后来习惯在结构体或注释里明确写明：

// x: 行号, y: 列号 rowCnt[x]++; colCnt[y]++;

虽然多写几个注释看起来不起眼，但能帮你在调试时省下大量时间。

4.5 这个套路还能用在哪里

环形均分纸牌加中位数贪心，不是一道题用完就扔的模型。它本质上是“在一维环状结构上让每个位置达到均匀状态”的通用解法。

• 如果题目变成环形排列的人需要交换座位，每家每户需要坐满固定人数，核心公式完全一样。
• 如果问题从环变成链，答案就是前缀和的绝对值之和，不需要中位数，直接扫描。
• 如果问题变成二维网格的均分，先检查行、列可不可分，再把两个一维答案相加，这种“降维 + 独立求解”的思想在很多网格题里都能复用。

我后来做类似的习题时，基本形成了一个条件反射：只要看到环形结构，第一反应不是模拟，而是考虑能不能切开；切开后如果答案是“某个常数所有前缀和偏移量求和”，第二反应就是中位数贪心。

最后分享一个我自己的体会：这种数学结论型算法题，光背代码很容易忘，关键是理解“切断点”和“前缀和”的对应关系。第一次看中位数解法时，我也觉得为什么不是平均值，明明平均数才是“最中间”的那个数。但画一画绝对值函数图像之后，我彻底明白了：绝对值求和的导数特征决定了中位数才是平衡点。此后遇到任何“最小化到若干点距离之和”的题，我都条件反射先想中位数，而不是平均值。如果你也卡在类似的地方，建议动手画一次 f(c)=|c-1|+|c-5|+|c-10| 的曲线，比看十篇题解都管用。