做这道题之前我一直觉得“环形均分纸牌”和“中位数贪心”是两套互不相干的知识点一个负责模拟搬运过程一个负责在数轴上找最优位置。直到完整刷完 P10453 七夕祭我才意识到这两个东西其实是一体两面——前者给出问题模型后者给出数学答案。这篇文章我把自己的推导过程和踩坑记录都放出来希望帮你一次性吃透这个组合套路。如果你正在备战 CSP/NOIP或者刚开始刷洛谷的经典题P10453 是一个非常好的观测样本。它表面上是二维网格上的复杂交换问题但抽掉外壳后发现核心不过是一维环形均分纸牌而且行方向和列方向完全独立。理解了这个你不仅会做这一道题还会顺带掌握一大类“把环切开成链”的贪心证明方法。1. 题目本质拆解看似二维实则是两条独立的环形均分纸牌1.1 先看懂交换操作到底在干什么七夕祭的题面给了一个 n 行 m 列的网格里面有一些特殊摊位。你只能做一种操作交换相邻两个格子里的东西。相邻包括上下相邻和左右相邻每次交换代价为 1。我一开始想复杂了以为这是在网格上做二维匹配。实际上你盯住某个特殊摊位看交换相邻格子本质就是让这个特殊摊位在网格上往上下左右移动一格。如果一个格子是空的那一次交换就等价于特殊摊位瞬移一步即使两个格子都有特殊摊位交换也只是让两个特殊摊位同时向对方方向各移动一步总代价依然可以按每个特殊摊位走过的路径长度来理解。这个视角非常关键。因为它把操作从“抽象的格子交换”翻译成了“棋子在网格上移动”后面才能把行、列分开看。1.2 行和列为什么能拆开算现在考虑两类操作上下交换改变特殊摊位所在的行但不改变它所在的列。左右交换改变特殊摊位所在的列但不改变它所在的行。这意味着如果你想调整第 i 行和第 i1 行的特殊摊位数量只能用上下交换左右交换完全帮不上忙。同理调整第 j 列和第 j1 列的数量只能用左右交换。所以一个 n×m 的二维问题直接退化成了两个一维问题行方向上的均分纸牌和列方向上的均分纸牌。两者用的操作不同互相不干扰最终答案就是两个一维答案相加。这里要注意一个细节有人会问我先做左右交换再做上下交换会不会导致前面白做了不会。因为上下交换不改变每行的总数左右交换不改变每列的总数两个维度的进度可以被同时推进。就像你同时整理书架的两层虽然每次只能动一本书但整理上层和整理下层是完全独立的两件事。1.3 可行性判定整除条件优先于一切在算最小步数之前必须先回答“能不能做到”。要让每一行特殊摊位数量相等必须满足总摊位数量 t 能被行数 n 整除。要让每一列特殊摊位数量相等必须满足总摊位数量 t 能被列数 m 整除。于是分成四种情况条件输出t % n ! 0 且 t % m ! 0impossiblet % n ! 0 且 t % m 0column 最小步数t % n 0 且 t % m ! 0row 最小步数t % n 0 且 t % m 0both 最小步数这个判定必须在调用核心函数之前做。我见过有同学在 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 和第 i1 堆之间的边界向右传递如果 s[i] 0说明前 i 堆缺少的牌必须从右边越过边界补进来。总之第 i 和第 i1 堆之间最少要移动的牌数就是 |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 个或者第 (n1)/2 个元素都行因为偶数个时中间两个数之间的整个区间都是最优解。2.4 把公式落到代码端前缀和中位数法环形均分纸牌的完整算法流程就非常清晰了计算平均数 avg。对 i 从 1 到 n计算 s[i] s[i-1] a[i] - avg。把 s[1] 到 s[n] 这 n 个值排序。取中位数 mid。答案 Σ|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; vectorint 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 开始编号所以数组开 n1 和 m1 的大小。不要混用行数组的大小是 n1列数组的大小是 m1一旦搞反越界访问在本地可能不明显在 OJ 上就会随机 RE 或者 WA。3.2 核心函数环形均分纸牌的板子直接封装一个函数传入一维计数数组和它的长度返回最小操作次数。如果余数不为 0返回 -1 表示不可行。long long ringDivide(vectorint cnt, int len, int total) { if (total % len ! 0) { return -1; } int avg total / len; vectorlong long s(len 1, 0); for (int i 1; i len; i) { s[i] s[i - 1] cnt[i] - avg; } vectorlong 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 级别加总后可能到 1e10int 必爆。为什么排序后取 len/2 而不是 (len1)/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 手算验证一个完整样例我构造一个例子n3, m3, t3三个特殊摊位在 (1,2), (2,2), (3,3)。行计数数组rowCnt[1]1, rowCnt[2]1, rowCnt[3]1t%n0平均数是 1。计算前缀和s[1]0, s[2]0, s[3]0排序后中位数是 0行方向答案 0。没错每行本来就已经各有一个不需要操作。列计数数组colCnt[1]0, colCnt[2]2, colCnt[3]1t%m0平均数也是 1。差值序列是 -1, 1, 0前缀和 s[1]-1, s[2]0, s[3]0等一下这里要算清楚s[1] 0 - 1 -1s[2] s[1] 2 - 1 0s[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[(len1)/2] 作为中位数那是在某种线性公式里常用的写法。但环形版本我用的是包含 s[len] 的一组前缀和元素个数是 len。当 len 为偶数时s[(len1)/2] 取的是偏左的位置而 s[len/2] 取的是偏右的位置两者都能得到最优值。问题不在这。真正的问题是如果你在构造 vals 时不小心漏掉了 s[len] 这一项只 push 了 s[1] 到 s[len-1]那么元素个数变成 len-1中位数的“第 k 小”语义就全变了。尤其在 len 为偶数时漏一个数可能会导致答案差出好几倍。我建议每次写完都用一个 len2 或 len4 的小样例手推验证。4.2 整除判定放错了顺序有同学先算出平均数 avg t / n然后再判断 t % n 是否为 0。这个顺序在 C 里很危险因为整数除法直接截断小数后续的前缀和计算基于一个假的平均数值整个差值体系都是错的。正确做法是先判断余数再计算平均数。我在本地测试时用过 t7, n3 的数据如果真的先除后判平均数是 2差值前缀和算出来一个看似合理的结果但在 OJ 上必然 WA。这种错误非常隐蔽因为它不会报溢出或者越界只是结果不对。4.3 前缀和数组需要单独开 long long计数数组本身是 int 没问题因为每个位置最多 t 个t 一般不超过 1e5。但前缀和一旦累加就可能超出 int 范围。举一个极端例子如果 t1e5n1所有差值都集中在同一项观察 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| 的曲线比看十篇题解都管用。