环形均分纸牌看到这个名词刷过洛谷P10453七夕祭的人应该都懂那种感觉原本就是一群人围成一圈发牌的问题偏偏要套进一个二维网格、还要同时满足行和列的约束一上来很容易被题面唬住。尤其“中位数贪心”五个字听着像玄学实际上拆开之后就是前缀和加排序逻辑非常朴素。我这几天把七夕祭反复做了几遍也算把一维、环形、二维三层关系彻底捋顺了。这篇就顺着这个思路来先从最简单的线性均分纸牌讲起推一遍前缀和怎么做再把环放开解释清楚为什么中位数就是最优的断点最后回到七夕祭看看两个维度为什么能拆开算、答案为什么直接相加。文末会给一份可以直接照抄的C实现也把我踩过的几个坑一并列出来。这篇东西适合刚接触贪心和前缀和的选手也适合已经会写模板、但没想明白其中原理的老铁。1. 七夕祭到底在求什么题面拆解与结论先行1.1 题面在说什么P10453七夕祭的题面很喜庆七夕节集市上有一个网格状的场地场地里摆了一些摊位一次操作可以把某个摊位移动到它上下左右的相邻空格里。问最少操作多少次能让每一行的摊位数相同同时每一列的摊位数也相同。更形式化一点有一个 n 行 m 列的网格一共 t 个摊位。读完输入后我们手里其实只有两类信息第 i 行里有多少个摊位 row[i]第 j 列里有多少个摊位 col[j]。至于摊位具体在列内的哪个位置、行内的哪个位置都不影响最终答案这正是题目简化后变成算法题的关键一步。很多第一次接触这道题的人会往BFS、最短路甚至网络流方向去想毕竟“移动最少步数”听起来像路径规划。但仔细读题会发现摊位的初始位置本身没有障碍物限制每个格子最多一个摊位也不影响均分模型因为移动的本质只是改变行列分布。你不需要真的模拟每个摊位的移动轨迹你只需要算清楚“某一维度上目标数量和当前数量差了多少”。1.2 什么时候无解先看整除关系判断可行性很简单但很容易漏行方向要可行必须满足 t % n 0因为每行目标摊位数是 t / n总摊位必须能被行数整除。列方向要可行必须满足 t % m 0理由同上。注意是分别判断。可能出现行方向可行、列方向不可行的情况也可能反过来。甚至两个方向都不可行。题目输出的四种情况就对应到这里情况输出行、列都可行both 总步数只有行可行row 行方向步数只有列可行column 列方向步数行、列都不可行impossible这里有个最常见的输出错误只要有一个方向不可行就输出 impossible。这是不对的。题目问的是能不能让每行摊位数相同且每列摊位数相同所以只有当两个方向都做不到时才是不行。只要有一个方向能做到那你至少可以把那个方向调整好输出对应的结果。1.3 全题的解题骨架拆成两个独立问题这道题之所以能成为经典是因为它可以拆成两个几乎完全独立的子问题纵向移动只影响行分布横向移动只影响列分布。所以“行方向达到均分所需的最小纵向步数”和“列方向达到均分所需的最小横向步数”互不干扰。总答案就是两个子问题的答案相加。而每一个子问题都恰好是一个环形均分纸牌模型。也就是说你只要能在 O(n log n m log m) 的时间内把下面这个函数写好给定一个长度为 k 的数组 cnt总和为 sum如果 sum % k ! 0 则无解 否则求环形均分纸牌的最小代价。七夕祭就结束了。是不是听起来很简单但很多人恰恰卡在“为什么每一维是环形”和“中位数到底怎么用”这两件事上。下面两章就是专门把这两块掰开揉碎。2. 先解决一维线性均分纸牌的前缀和思路2.1 线性模型的平衡方程假设 n 个人排成一排第 i 个人手上有 a[i] 张纸牌总数为 SS % n 0目标平均数是 avg S / n。每次操作只能从相邻的两个人之间传递纸牌问最少传递多少张。我们设 x[i] 表示第 i 个人传给第 i1 个人的纸牌张数。如果 x[i] 是负数就表示第 i1 个人反向传给第 i 个人。那么第 i 个人最终的牌数可以写成a[i] - x[i] x[i-1] avg这里 x[0] 表示“第 0 个人传给第 1 个人”在线性模型里它就是 0因为没有人站在第 1 个人左边。x[n] 同理也必须是 0因为第 n 个人右边没人。把式子整理一下x[i] x[i-1] a[i] - avg这个递推式非常关键。它告诉我们一旦起点 x[0] 确定整条链上所有相邻传递量就全部唯一确定了。在线性模型里 x[0] 固定为 0所以没有任何优化空间顺着递推一路算到底就是唯一的可行方案答案就是这些传递量绝对值的和。2.2 前缀和的几何意义令 d[i] a[i] - avg表示每个人相对平均数的“盈余”正数代表多出来负数代表缺了。再令 s[i] 为 d[i] 的前缀和s[i] d[1] d[2] ... d[i]那么由上面的递推式立刻得到x[i] s[i]换句话说第 i 个人和第 i1 个人之间必须传递的净张数恰好等于前 i 个人的盈余累积和。整个问题的答案就是ans |s[1]| |s[2]| ... |s[n-1]|注意最后一项 s[n] 一定是 0因为所有盈余加起来正好抵消所以不用加。为什么这个贪心是对的因为相邻两人之间的净流量是平衡方程直接解出来的不是我们“选择”出来的。任何可行方案都必须让这些边界上流过这么多牌多一点少一点都不可能同时满足所有人恰好达到 avg。因此这个下界既是下界也是可达到的方案。2.3 手算一个完整例子举个具体的例子n 4a [1, 2, 3, 6]。总数 S 12avg 3。d [-2, -1, 0, 3]。前缀和依次为s[1] -2s[2] -3s[3] -3所以答案为 2 3 3 8。对应的实际方案是什么x[3] -3表示第 4 个人要给第 3 个人 3 张牌。x[2] -3表示第 3 个人要给第 2 个人 3 张牌。x[1] -2表示第 2 个人要给第 1 个人 2 张牌。整个传递链条一共用了 8 张牌4号先给3号3张3号再给2号3张2号再给1号2张。你可以自行验证最终所有人的牌数都是3。3. 中位数贪心环形均分纸牌的核心推导3.1 环带来的自由度断点不再固定线性模型把第 1 个人左边和第 n 个人右边都封死了所以 x[0] 只能等于 0。但是环形模型不一样n 个人围成一圈第 n 个人和第 1 个人也是邻居。这时候 x[0] 就有了意义——它是第 n 个人传给第 1 个人的张数这个值不能再被假设为 0它可以取任意值。同样的递推式依然成立x[i] x[0] s[i]其中 x[0] 是我们引入的“第0个人给第1个人”的流量s[i] 仍然是盈余前缀和范围是 i 1 到 n。注意 s[n] 0所以 x[n] x[0]这正好对应第 n 个人传给第 1 个人的流量环在这里闭合。总代价变成f(x[0]) |x[0] s[1]| |x[0] s[2]| ... |x[0] s[n]|我们的目标就是在 x[0] 可以任意取的情况下让这个函数最小。这就是环形均分比线性均分多出来的优化空间。3.2 为什么取中位数最优把问题换个写法。令 c[i] -s[i]那么代价就是f(t) |t - c[1]| |t - c[2]| ... |t - c[n]|这就是经典的“到给定点的距离和最小”问题给你 n 个点选一个位置 t让所有点到 t 的距离之和最小。答案就是取这 n 个点的中位数。证明也不难。假设 t 向右移动一小段距离 δ那么所有位于 t 左边的点它们到 t 的距离都会增加 δ所有位于 t 右边的点距离都会减少 δ。如果左边有 k 个点右边有 n - k 个点那么总代价的变化量就是δ × (k - (n - k)) δ × (2k - n)当 k n/2 时2k - n 0说明继续向右移动会让总代价下降所以 t 应该右移当 k n/2 时继续右移反而会让代价上升所以应该左移。平衡点恰好发生在 k ≈ n/2 的时刻也就是中位数的位置。如果是奇数个点中位数唯一如果是偶数个点中间两个点之间的任意位置都能达到同样的最小代价。实际写代码时取中间两个的任意一个都行因为答案相同。换回我们的原变量最优的 x[0] 等于 -s[i] 的中位数也等价于让 s[i] 整体向它们的中位数收缩。最终代码里你不需要真的去求 -中位数直接对 s 数组排序然后计算 Σ|s[i] - 中位数| 就完事了。3.3 手算糖果传递模型经典的糖果传递洛谷P2512就是纯环形均分纸牌。看一个 5 人例子a [1, 2, 3, 4, 5]。总数 S 15avg 3。d [-2, -1, 0, 1, 2]。前缀和s[1] -2s[2] -3s[3] -3s[4] -2s[5] 0对 [-2, -3, -3, -2, 0] 排序得到 [-3, -3, -2, -2, 0]中位数是 -2。答案|-2 - (-2)| |-3 - (-2)| |-3 - (-2)| |-2 - (-2)| |0 - (-2)| 0 1 1 0 2 4这个答案对应的实际方案也很清楚x[0] 2也就是第 5 个人先给第 1 个人 2 张。接着第 4 个人给第 3 个人 1 张第 3 个人给第 2 个人 1 张。总共传递 4 张牌所有人都变成 3 张。注意这里 s[5] 0 也必须参与排序和求和它对应的是“第 5 个人传回第 1 个人”的那一环流量。这也是环形和线性在实现上最容易被忽略的差别线性只累加前 n-1 个前缀和环形要全部 n 个都算进去。4. 行列独立为什么两个环形均分可以直接相加4.1 纵横向移动互不干扰现在回到七夕祭。假设我们已经求出了行方向的最小纵向步数 R也就是让每行摊位数相等的最少上下移动次数。列方向的最小横向步数 C也就是让每列摊位数相等的最少左右移动次数。为什么总答案就是 R C从操作角度看一次移动要么是上下移动要么是左右移动。上下移动只会改变某一行和它相邻行的摊位数分布完全不影响每一列的统计值左右移动同理只改变列分布不影响行的统计。所以纵向移动总量构成行均分问题的一个下界横向移动总量构成列均分问题的一个下界两个下界互不相干。更重要的一点是这两个下界可以同时达到。你可以这样构造方案先不管列目标只做纵向移动把每一行都调整到目标数量然后再做横向移动把每一列调整到目标数量。由于第二步左右移动不会破坏已经完成的行均分所以两个方向的最优解可以简单相加不会有任何冲突。这就是“纵向只做行的事横向只做列的事”的直观含义。4.2 为什么每一维都是环形模型这是初看七夕祭时最困惑的一点网格是一个矩形第一行和最后一行并不相邻为什么行方向的计算用的是环形均分纸牌而不是线性均分纸牌答案就藏在二维网格的自由度里。在线性均分纸牌中第 1 个人和第 n 个人之间没有传递通道所以 x[0] 被锁死为 0。但在二维网格中行之间的传递不是只发生在固定的“边界”上。一个摊位如果要从第 n 行回到第 1 行它可以先横向移动到任意一列再进行纵向的逐步移动。列方向的自由度让行方向的首尾在数学模型上闭环了。这也是七夕祭的场地设定——或者更准确地说这类二维均分题的标准抽象——把行看成一个环把列也看成一个环。你不妨这样记忆看到“二维网格 均分 最小移动步数”第一反应就是把行、列拆开每一个方向都当作一个环形均分纸牌来解。这个套路在竞赛题里出现频率非常高包括一些变体题本质上都没有跳出这个框架。4.3 一类题的识别信号掌握一个模型远比背一道题有用。下面几个特征同时出现时很大概率就是在考环形均分纸牌加中位数贪心数据对象可以按某个维度统计成数组比如行、列、位置、编号。每次“移动”只改变一个维度的分布。目标是让每个统计桶的数量都相等。求最小总移动量。一旦认出这个结构先检查整除性然后直接套用前缀和、排序、取中位数三件套正确率和速度都会非常可观。5. 完整实现calc函数与主流程代码5.1 核心函数 calc 逐行拆解看一下关键代码我用了 C17核心逻辑全部封装在一个函数里方便复用。#include bits/stdc.h using namespace std; using ll long long; // cnt: 长度为 k 的数组表示每一行/每一列当前拥有的摊位数量 // sum: 摊位总数 // 返回该方向环形均分纸牌的最小步数无解返回 -1 ll calc(const vectorll cnt, ll k, ll sum) { if (sum % k ! 0) return -1; // 无法均分 ll avg sum / k; vectorll pref(k 1, 0); for (int i 1; i k; i) { pref[i] pref[i - 1] cnt[i - 1] - avg; } vectorll vals(pref.begin() 1, pref.end()); // 取出 pref[1..k] sort(vals.begin(), vals.end()); ll mid vals[k / 2]; // 中位数偶数取中间靠右那个即可 ll ans 0; for (ll v : vals) { ans llabs(v - mid); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n, m, t; cin n m t; vectorll row(n, 0), col(m, 0); for (int i 0; i t; i) { ll x, y; cin x y; x--; y--; row[x]; col[y]; } ll ansRow calc(row, n, t); ll ansCol calc(col, m, t); if (ansRow -1 ansCol -1) { cout impossible\n; } else if (ansRow -1) { cout column\n ansCol \n; } else if (ansCol -1) { cout row\n ansRow \n; } else { cout both\n ansRow ansCol \n; } return 0; }这个 calc 函数就是整道题的心脏。来逐行解释它的逻辑。第一步判断 sum % k ! 0。这一步直接代表“该方向是否可行”返回值 -1 只是一个标记因为真正的最小步数永远非负。主函数用 -1 来区分“不可行”和“答案是 0”两个语义完全不一样。第二步构造 pref 数组。pref[i] 的含义是前 i 个统计桶的盈余累积和也就是前面推导里的 s[i]。注意循环里是 cnt[i-1] 减去 avg因为 cnt 是 0 下标数组pref 是 1 下标数组。这一步如果写成 cnt[i] 会直接越界或者漏算一个元素属于最常见的低级错误。第三步把 pref[1] 到 pref[k] 取出来排序。这里必须包含 pref[k]也就是最后一个前缀和 0。如果你图省事直接对 pref 排序会把 pref[0] 也排进去导致中位数偏掉答案必错。所以代码里单独构造了 vals。第四步取中位数。vals[k/2] 在 k 为偶数时是中间两个里的右边那个在 k 为奇数时就是唯一中位数。理论上偶数时取左边那个也行答案完全一样。有些模板会写 vals[(k-1)/2]本质没有区别。最后累加每个前缀和到中位数的绝对差返回答案。这一步就是环形均分纸牌的全部优化。5.2 主程序与分类输出主程序的逻辑很简单读入 n、m、t。初始化和统计行、列数组。读入 t 个坐标注意题目给的是 1-based 坐标读进来要减 1 再进数组。分别对行方向、列方向调用 calc。判断两个返回值是否为 -1按四种情况输出。输出的时候要注意换行。洛谷这类题通常要求先输出类型字符串再换行输出答案所以cout row\n ansRow \n这种写法没问题。如果你在用 Python思路完全一样只是注意 Python 的 int 没有溢出问题排序和累加都很直接这里就不单独给完整代码了。5.3 复杂度与数据范围calc 函数内部只有一次排序所以复杂度是 O(k log k)。两个方向分别排序总复杂度 O(n log n m log m)对于 n、m 在 10^5 甚至 10^6 级别的数据完全没有压力。空间上只需要 row、col、pref、vals 四个数组前两个长度分别是 n 和 m后两个最多也是 n 或 m 级别同样很小。但有一个数据范围问题必须强调答案可能非常大。如果 t 很大且网格很狭长横向或纵向的总移动步数可能轻松超过 32 位整数的范围。所以所有涉及答案的变量都用 long long包括前缀和、中位数、绝对值累加。我见过有人用 int 存答案结果样例全过、大数据直接WA排查半天才发现是溢出。6. 实战避坑常见问题与易错点速查6.1 高频跳坑清单我把自己做这题时踩过、以及后来帮别人 debug 时见到的坑整理成了一张表按出现频率排序坑点错误写法正确做法后果可行性判断短路只要 t%n ! 0 或 t%m ! 0 就输出 impossible两个方向分别判断漏掉 row 或 column 的情况环形前缀和漏最后一项只循环 i 1 到 k-1必须算到 pref[k]且 vals 包含 pref[k]中位数偏一个位置答案错误中位数下标乱取偶数时取中间两个的平均值取中间两个任意一个累加结果相同平均写法容易引入浮点误差前缀和数组混入 pref[0]直接对 pref 排序单独复制 pref[1..k] 再排序中位数多了一个点统计数组越界读入坐标后直接 row[x]先 x--, y--越界或统计串位int 溢出答案用 int 存用 long long大数据出错其中最隐蔽的其实是“环形前缀和漏最后一项”这个坑。漏掉 pref[k] 会让整个中位数计算建立在残缺的数据点上。比如第 3.3 节的例子如果不算 pref[5] 0排序结果变成 [-3, -3, -2, -2]中位数会是 -2.5 这类尴尬值累加结果和正确答案就不一样了。6.2 一个容易混淆的变体有时题目会把均分纸牌出成线性的比如一行小朋友传递糖果首尾不相连。这时答案是 Σ|s[i]|i 1 到 n-1不取中位数。而环形模型多了一个优化维度才需要取中位数。这两者的关系是线性是环形的特例相当于强制 x[0] 0环形把 x[0] 放开让整个环可以选择一个最合适的“断点”去剪开。理解了这一点你就不会再背错公式。看到首尾相邻就做中位数看到首尾不相邻就直接累加前缀和绝对值。6.3 如果还想深入多约束变体七夕祭是两个独立的一维环形均分纸牌。遇到更复杂的题可能有三四个维度或者维度和维度之间有耦合。不管怎么变处理思路都一样先看每次操作改变哪些维度再看哪些维度可以独立优化最后把各维度的下界加起来判断能否同时达到。如果某一个维度不能均分通常整个问题就无解。另外中位数贪心不止出现在均分纸牌里。一维货仓选址、带权中位数、甚至有些区间覆盖问题最后都会归结到“让一组点到某个点的距离和最小”。你在竞赛里只要见到“最小化绝对差之和”中位数就是第一个应该考虑的答案。最后多说一句我自己最开始做七夕祭时下意识以为是道搜索题抱着 BFS 的想法琢磨了很久越写越复杂后来看了题解才反应过来原来这题考的是均分纸牌和中位数贪心。从那以后我总结出一个习惯碰到“移动格子”“传递物品”“分配数量”这类题先别急着模拟每种状态先把一维统计数组画出来看看是不是标准的环形均分模型。往往图画完答案的轮廓就已经出来了。这篇里的 calc 函数我建议你直接存进模板里因为它在行方向、列方向、以及各种一维均分题里都能复用。等你在洛谷再遇到披着不同外衣的类似题时就知道这个模板有多香了。