环形纸牌问题

$\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)$
• $A_n - a_n + a_1 = M \Rightarrow a_1 = M - A_n + a_n = a_1 - \sum\limits_{i = 1}^n A_i + M \times n = a_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) $$

显然，当 $a_1$ 为 $C$ 的中位数时，该式有最最小值。

于是每一组数据就都可以 $\mathcal{O}(n)$ 解决了。