【学习笔记】环形均分纸牌问题
lixuanyan
·
·
题解
\texttt{Description}
有 n 个人坐成一圈，每个人有 a_i 张牌，每个人可以给自己相邻的人一些牌。求出至少有多少张牌需要传递以使他们每个人所拥有的牌数一样。
\texttt{Solution}
设每个人都有 A_i(1 \leq i \leq n) 张牌，则每个人的目标牌数都是 M = \sum\limits_{i = 1}^n A_i \div n。设第 i 个人给第 i - 1 个人 a_i 张牌，特殊地：
- 当 a_i \le 0 时，表示第 i- 1 个人给第 i 个人 \lvert a_i \rvert 张牌。
- 当 i = 1 时，表示第 1 个人给第 n 个人 a_i 张牌。
那么很显然，有以下结论：
-
A_1 - a_1 + a_2 = M \Rightarrow a_2 = M - A_1 + a_1 = a1 - (A_1 - M)
-
A_2 - a_2 + a_3 = M \Rightarrow a_3 = M - A_2 + a_2 = M - A_2 + a_1 - A_1 + M = a_1 - (A_1 + A_2 - 2M)
-
A_3 - a_3 + a_4 = M \Rightarrow a_4 = M - A_3 + a_3 = M - A_3 + a_1 - A_1 - A_2 + 2M = a_1 - (A_1 + A_2 + A_3 - 3M)
-
\cdots
-
A_{n - 1} - a_{n - 1} + a_n = M \Rightarrow a_n = a_1 - (A_1 + A_2 + A_3 + \cdots + A_{n - 1} - M \times (n - 1))
-
而这题，我们只需要求出 \sum\limits _{i = 1} ^n\lvert a_i\rvert 的值即可。我们不妨设 C_i = \sum\limits _{j = 1} ^i A_i - M \times i，那么就可以得到：
a_{i + 1} = a_1 - C_i
所以，我们需要求的内容就转化为：
\min(\lvert a_1 - 0 \rvert + \lvert a_1 - C_1\rvert + \lvert a_1 - C_2\rvert + \cdots + \lvert a_1 - C_{n - 1}\rvert)
则可以令 C_n 为 0，显然，当 a_1 的值等于 C_{1\cdots n-1} 的中位数时，该式有最小值。
于是每一组数据就都可以 \mathcal{O}(n) 解决了。
当然，还有第二种方法解决本类问题。
我们发现，对于一般的均分纸牌问题，就相当于把第 n 个人和第 1 个人断开。此时，令他们每个人拥有的牌的数量减去 M \times i 是 A_{1\cdots n}，前缀和是 S_{1\cdots n}。如果在第 k 个人之后把环断开呢？此时，每个人拥有的牌数就是：A_{k + 1}，A_{k + 2}，\cdots，A_n，A_1，\cdots，A_k。而前缀和是：S_{k + 1} - S_k，S_{k + 2} - S_k，\cdots，S_n - S_k，S_1 + S_n - S_k，\cdots，S_k + S_n - S_k。
对于一般的均分纸牌问题，答案是 \sum\limits_{i = 1}^n\lvert S_i\rvert，那么经过上面的分析，环形均分纸牌的答案就显然是 \sum\limits_{i = 1}^n\lvert S_i - S_k\rvert。
有人可能会问，如何保证将环断开之后做法的正确性呢？证明如下：
首先两个相邻点之间的流向是固定的，所有边的流向不可能都一致。
那么环可以划分成若干个同向边组成的极长链，对于一条链可以内部达到平衡，所以整个链我们可以缩成一条边，对应这条边的方向。
缩完之后整个图的点数一定是偶数。
现在我们假设存在一个最优解使得环上的每条边都有流量，那么我们把流量最小的边即为 1 号边，并按环的顺序依次标号。可以通过奇数边增流，偶数边退流或者奇数边退流偶数边增流的方式调整答案知道 1 号边流量为 0。
该证明过程来自 @7KByte，并征求过其意见。
推荐习题：
- P2125 图书馆书架上的书
- P2512 [HAOI2008]糖果传递
- P4016 负载平衡问题
- UVA11300 Spreading the Wealth
其中，对于 P2125，我们需要有序地输出每一个 a_i 的值，而计算中位数由于需要排序，所以会打乱 C 原有的顺序，也就无法按照原来顺序计算 a_i 。因此，我们可以建立一个临时数组计算中位数。在输出的时候，题目要求输出第 i 个给了第 i - 1 和 i + 1 分别多少个，而 a_i 表示的是第 i 个人给第 i - 1 个人的数量，所以输出的时候需要分别输出 a_i 和 -a_{i + 1}。特殊地，a_{n + 1} 的值应该是 a_1（想一想，为什么）。
对于另外三题，按照正常的思路和解答方式即可，方法一致。