AcWing 105. 七夕祭
题目链接：105. 七夕祭 - AcWing题库
经过分析，我们可以发现，交换左右两个相邻的摊点只会改变某两列中 cl 感兴趣的摊点数，不会改变每行中 cl 感兴趣的摊点数。
同理，交换上下两个相邻的摊点只会改变某两行中 cl 感兴趣的摊点数，不会改变每列中 cl 感兴趣的摊点数。
所以我们可以把本题分成两个互相独立的部分计算。
- 通过最少次数的左右互换使每列中 cl 感兴趣的摊点数相同。
- 通过最少次数的上下交换使每行中 cl 感兴趣的摊点数相同。
以第 1 个问题为例进行探讨。
我们可以统计处在初始情况下，每列中 cl 感兴趣的摊点总数，记为 $C[1] \sim C[M]$。
若 cl 感兴趣的摊点总数 $T$ 不能被 $M$ 整除，则不可能达到要求。
若 $T$ 能被 $M$ 整除，则我们的目标就是让每列中有 $T/M$ 个 cl 感兴趣的摊点。
思考到这里，读者可能已经想到了一个与此类型的经典问题 “均分纸牌”。“均分纸牌” 问题是说，有 $M$ 个人排成一行，他们手中分别有 $C[1] \sim C[M]$ 张纸牌，在每一步操作中，可以让某个人把自己手中的一张纸牌交给他旁边的一个人，求至少需要多少步操作才能让每个人手里持有的纸牌数相等。
显然，当所有人手中持有的纸牌总数 $T$ 能被 $M$ 整除时，“均分纸牌” 问题有解，在有解时，我们可以先考虑第一个人。
- 若 $C[1] > T / M$，则第一个人需要给第二个人 $C[1] - T / M$ 张纸牌，即把 $C[2]$ 加上 $C[1] - T / M$。
- 若 $C[1] < T / M$，则第一个人需要从第二个人手中拿 $T / M - C[1]$ 张纸牌，即把 $C[2]$ 减去 $T / M - C[1]$。
按照同样的方法，依次考虑第 $2 \sim M$ 个人。
即使在某个时刻有某个 $C[i]$ 被减为负数也没有关系，因为接下来 $C[i]$ 就会从 $C[i + 1]$ 处拿牌，在实际中可以认为 $C[i]$ 从 $C[i + 1]$ 处拿牌发生在 $C[i - 1]$ 从 $C[i]$ 处拿牌之前。
按照这种方法，经过计算，达到目标所需要的最少步数其实就是：
\[\sum_{i = 1}^M{\lvert i * {T \over M} - G[i] \rvert}，其中 G 是 C 的前缀和，即 G[i] = \sum_{j = 1}^i{C[j]}\]其含义是每个 “前缀” 最初共持有 $G[i]$ 张纸牌，最终会持有 $i * T / M$ 张纸牌，多退少补，会与后面的人发生 “二者之差的绝对值” 张纸牌的交换。
如果我们设 $A[i] = C[i] - T / M$，即一开始就让每个人手中的纸牌数都减掉 $T / M$，并且最终让每个人手里都恰好有 $0$ 张纸牌，答案显然不变，就是：
\[\sum_{i - 1}^M{\lvert S[i] \rvert}，其中 S 是 A 的前缀和，即 S[i] = \sum_{j = 1}^i{A[j]}\]回到数学的角度，以上两个公式也可以互相推到得到。
回到本题，如果不考虑 “第 1 列与最后一列也是相邻的” 这一条件，那么刚才提到的本题中的第 1 个问题与 “均分纸牌” 问题是等价的。
若问题有解，一定存在一种适当的顺序，使得每一步传递纸牌的操作可以转化为交换一对左右相邻的摊点（其中 cl 恰好对这两个摊点之一感兴趣）。
若第 $1$ 列与最后一列相邻，则问题等价于一个 “环形均分纸牌”。
仔细思考可以发现，一定存在一种最优解的方案，环上某两个相邻的人之间没有发生纸牌交换操作。
于是有一种朴素的做法是，枚举这个没有发生交换的位置，把环断开看成一行，转化为一般的 “均分纸牌” 问题进行计算。
首先，一般的 “均分纸牌” 问题就相当于在第 $M$ 个人与第 $1$ 个人之间把环断开，此时这 $M$ 个人写成一行，其持有的纸牌数、前缀和分别是：
| $A[1]$ | $S[1]$ |
| $A[2]$ | $S[2]$ |
| $\cdots$ | $\cdots$ |
| $A[M]$ | $S[M]$ |
如果在第 $k$ 个人之后把环断开写成一行，这 $M$ 个人持有的纸牌数、前缀和分别是：
| $A[k + 1]$ | $S[k + 1] - S[k]$ |
| $A[k + 2]$ | $S[k + 2] - S[k]$ |
| $\cdots$ | $\cdots$ |
| $A[M]$ | $S[M] - S[k]$ |
| $A[1]$ | $S[1] + S[M] - S[k]$ |
| $\cdots$ | $\cdots$ |
| $A[k]$ | $S[k] + S[M] - S[k]$ |
注意：此处 $A$ 是减去最终每个人手里纸牌数 $T / M$ 之后的数组，$A$ 数组均分之后每个人手里都有 $0$ 张纸牌，所以 $S[M] = 0$。
也就是说，从第 $k$ 个人把环断开写成一行，前缀和数组的变化是每个位置都减去 $S[k]$。
根据我们上面推导的公式，所需最少步数为：
\[\sum_{i = 1}^M{\lvert S[i] - S[k] \rvert}，其中 S 是 A 的前缀和，即 S[i] = \sum_{j = 1}^i{A[j]}\]当 $k$ 取何值时上式最小？这就是上一题 “货仓选址”！其中 $S[i]$ 是数轴上 $M$ 家商店的位置，$S[k]$ 是货仓的位置，$\lvert S[i] - S[k] \rvert$ 就是二者之间的距离。
根本不需要枚举 $k$，只需要把 $S$ 从小到大排序，取中位数作为 $S[k]$ 就是最优解！
至此，本题得到完美解决，时间复杂度为 $\mathcal{O}(N \log{N} + M \log{M})$。
综上所述，本题可类比为行、列方向上的两次 “环形均分纸牌” 问题。
环形均分纸牌又类比为 “均分纸牌” 和 “货仓选址” 问题。
其中的每一步都仅使用了基本算法和性质，最后转化为例简单而经典的问题。
完整代码：七夕祭.cpp