考虑 “纸牌均分问题” 如何解决？

设一共有 $M$ 个人，每个人初始的纸牌数量为 $c_i$，纸牌总数为 $T$

显然当 $M \nmid T$ 时，方案不存在，现只考虑方案存在的情况

第 1 个人为了达到平均持有数，需要向第 2 个人传递 $c_1 - T / M$ 数量的牌（正数是给，负数是拿）

第 2 个人为了达到平均持有数，需要向第 3 个人传递 $c_2 - T / M + c_1 - T / M$ 数量的牌

......

第 n-1 个人为了达到平均持有数，需要向第 n 个人传递 $\sum_{i=1}^{n-1} c_i - (n-1) \times T / M$ 数量的牌

此时前 n-1 人都达到了平均数，则第 n 个人必然也达到了平均数

统计易得，最小交换次数为：

$$ \sum_{i=1}^{n-1} \Big| { \sum_{j = 1}^i (c_j - \frac{T}{M}) } \Big| $$

不妨设 $A_i = c_i - T / M$，于是化简可得：

$$ \sum_{i=1}^{n-1} \Big| { \sum_{j=1}^i A_j } \Big| = \sum_{i=1}^{n-1} | { S_i } | \quad\text{其中 } S_i \text{ 为 } A_i \text{ 的前缀和，即 } S_i = \sum_{j=1}^i A_j $$

考虑 “纸牌均分问题” 如何延伸到 “环形纸牌均分问题” ？

环形区间的问题，第一想到的就是 破环成链 了

经过思考发现，一定存在一个最优解方案，环上有相邻的两个人之间没有发生交换

这部分证明如下：
如果环上相邻两人全部发生交换，则会出现两种情形：（正数传递为有向边的正向方向）

1. 出现一个环
   这种方案肯定不是最优解，因为给出去的纸牌经过一圈收回来了，显然浪费了操作次数
   我们在这个环上断开交易数量最小的一条交换边，并使其他边减少该边的交换数量，必然不会使方案变差
2. 出现一个点到达另一个点有两条路径
   我们可以断开起点两条出边中 $val = cnt \times w$ 最小的那一套边，并该边权值累加到另一条路径的每一条边上，其结果不会变差（其中 $cnt$ 是起点到终点路径上经过的点数，$w$ 是这条边的权重）

一个朴素的做法是直接枚举断点的位置，然后做一遍线性纸牌均分，但是时间复杂度为 $O(n^2)$ 不可取，需要推导

现将这 $n$ 个人的 $A_i$ 和 $S_i$ 罗列出来 $(A_i = \sum\limits_{j=1}^n (c_j - \dfrac{T}{M}), S_i = \sum\limits_{j = 1}^i A_j)$

$$ \begin{matrix} A_1 & S_1 \\\\ A_2 & S_2 \\\\ \cdots & \cdots \\\\ A_k & S_k \\\\ A_{k+1} & S_{k+1} \\\\ \cdots & \cdots \\\\ A_n & S_n \end{matrix} $$

考虑在第 $k$ 个人之后断开，则环化成链有：

$$ \begin{matrix} A_{k+1} & S_{k+1} - S_k \\\\ \cdots & \cdots \\\\ A_n & S_n - S_k \\\\ A_1 & S_1 + S_n - S_k \\\\ A_2 & S_2 + S_n - S_k \\\\ \cdots & \cdots \\\\ A_k & S_k + S_n - S_k \\\\ \end{matrix} $$

又易知 $S_n = \sum c_j - n \times T / m = 0$，故求得最小步数为：

$$ \sum_{i=1}^n |S_i - S_k| \quad\text{其中 } S_i \text{ 为 } A_i \text{ 的前缀和，即 } S_i = \sum_{j=1}^i A_j $$

该绝对值不等式最小值的求解，就同上一题 “货仓选址” 异曲同工了

因此 $S_k$ 的选择，就取 $S_i$ 排序后的中位数即可

第二种推导方式

这种推导方式相较于上一种，思维量小，但对公式的变形要求高，是直接统计每个点

考虑直接在环上求解，环的顺时针方向设为正方向，若边权为正，表示左向右传递；反之则是右向左传递

设 $d_i$ 表示第 $i$ 个人向第 $(i+1)\bmod n$ 传递的所有纸牌数量

传递完成后的结束是所有人的纸牌数量变成平均数，以此建立方程组有：

$$ \begin{cases} avg =& c_1 - d_1 + d_n \\\\ avg =& c_2 - d_2 + d_1 \\\\ \cdots \\\\ avg =& c_{n-1} - d_{n-1} + d_{n-2} \\\\ avg =& c_{n} - d_{n} + d_{n-1} \end{cases} \qquad \Rightarrow \qquad \begin{cases} d_1 &= c_1 - avg + d_n \\\\ d_2 &= c_2 - avg + d_1 \\\\ \cdots \\\\ d_{n-1} &= c_{n-1} - avg + d_{n-2} \\\\ d_n &= c_{n} - avg + d_{n-1} \end{cases} $$

观察易得，相邻两个等式之间，有可以代入的项，从上到下用滚动相消法可得：

$$ \begin{cases} d_1 =& c_1 - avg + d_n \\\\ d_2 =& \sum\limits_{i=1}^2 c_i - 2 \times avg + d_n \\\\ \cdots \\\\ d_{n-1} =& \sum\limits_{i=1}^{n-1} c_i - (n-1) \times avg + d_n \\\\ d_n =& \sum\limits_{i=1}^{n} c_i - n \times avg + d_n \end{cases} $$

易得通项：$d_i = \sum\limits_{j=1}^{i} c_j - i \times avg + d_n = d_n + \sum\limits_{j=1}^{i} (c_j - avg) = d_n - \sum\limits_{j=1}^{i} (avg - c_j)$

不妨设 $A_i = avg - c_i, S_i = \sum\limits_{j = 1}^i A_j$，则通项可以化简为：$d_i = d_n - \sum\limits_{j=1}^{i}A_j$

则总共的操作数为：

$$ \sum_{i=1}^n d_i = \sum_{i=1}^n |d_n - \sum_{j=1}^i A_j| = \sum_{i=1}^n |d_n - S_i| $$

由 绝对值不等式 易得：$d_n$ 应取 $S_i$ 排序后的中位数

long long calc(int c[], int n)
{
    int avg = t / n;
    for (int i = 1; i <= n; i ++ ) a[i] = c[i] - avg;
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    sort(s + 1, s + n + 1);
    long long res = 0;
    for (int i = 1; i <= n; i ++ ) res += abs(s[i] - s[(n + 1) / 2]);
    return res;
}

Code

#include <iostream>
#include <numeric>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int n;
int c[N];
LL s[N], a[N];

long long calc(int c[], int n)
{
    int avg = accumulate(c + 1, c + n + 1, 0ll) / n;
    for (int i = 1; i <= n; i ++ ) a[i] = c[i] - avg;
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    sort(s + 1, s + n + 1);
    long long res = 0;
    for (int i = 1; i <= n; i ++ ) res += abs(s[i] - s[(n + 1) / 2]);
    return res;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
    printf("%lld\n", calc(c, n));
    return 0;
}