形式化题目

给定一个长度为 $n$ 的环形序列 $a_1, a_2, \dots, a_n$，满足所有数之和能够被 $n$ 整除。 每次操作可以在相邻元素间传递 $1$ 单位数值，代价为 $1$。 求使序列中所有元素最终均等于平均数 $\bar{a} = \frac{1}{n} \sum_{i=1}^n a_i$ 的最小总代价。

正解

思路

本题是经典的「环状均分纸牌」问题。

1. 变量定义与平衡方程

设第 $i$ 个人给第 $i-1$ 个人传递了 $x_i$ 颗糖果（其中第 $1$ 个人向第 $n$ 个人传递 $x_1$ 颗；若 $x_i < 0$，表示第 $i-1$ 个人向第 $i$ 个人传递了 $-x_i$ 颗）。

对于第 $i$ 个人，最终持有的糖果数应为平均数 $\bar{a}$：

• 初始拥有 $a_i$ 颗；
• 给了第 $i-1$ 个人 $x_i$ 颗；
• 从第 $i+1$ 个人处得到了 $x_{i+1}$ 颗。

由此可列出每个人的平衡方程：

每传递一颗糖果的代价为 $1$，因此总代价为：

2. 代数递推与转化

将平衡方程移项变形：

依次展开所有变量，用自由变量 $x_1$ 表示其余所有 $x_i$：

令：

则有：

因此，目标函数可化简为：

3. 几何模型：数轴上的中位数

上式在几何上等价于：在数轴上有 $n$ 个固定点 $c_1, c_2, \dots, c_n$，我们需要选择一个实数点 $x_1$，使得 $x_1$ 到这 $n$ 个点的距离之和最小。

由绝对值函数的性质可知，$x_1$ 取点集 $c$ 的中位数时距离之和取得最小值。

4. 样例图示推演

以输入样例为例：$n = 4$，糖果数分别为 $[1, 2, 5, 4]$。

• 总糖果数为 $1 + 2 + 5 + 4 = 12$，平均数 $\bar{a} = 3$。
• 计算偏差 $a_i - \bar{a}$：$[-2, -1, 2, 1]$。
• 构造差值序列 $c$：
  • $c_1 = 0$
  • $c_2 = c_1 + (a_1 - \bar{a}) = 0 + (-2) = -2$
  • $c_3 = c_2 + (a_2 - \bar{a}) = -2 + (-1) = -3$
  • $c_4 = c_3 + (a_3 - \bar{a}) = -3 + 2 = -1$
• 得到数组 $c = [0, -2, -3, -1]$。
• 将 $c$ 排序后为 $[-3, -2, -1, 0]$。
• 取中位数 $x_1 = c[4 // 2] = c[2] = -1$。
• 计算总代价：$|-1 - (-3)| + |-1 - (-2)| + |-1 - (-1)| + |-1 - 0| = 2 + 1 + 0 + 1 = 4$。

flowchart LR
    c1["c3 = -3"] --- c2["c2 = -2"]
    c2 --- mid["x1 = -1 (中位数 c4)"]
    mid --- c3["c1 = 0"]

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21"""环状均分纸牌 / 糖果传递：前缀和转化为数轴上一点到各点的曼哈顿距离最小（中位数）。"""
import sys

def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 题面的 n
    a = [next(data) for _ in range(n)]
    avg = sum(a) // n
    # c[i] = S[i] - i * avg, 其中 c[0] = 0
    # 代价为 sum(|x_1 - c[i]|)，取 x_1 为 c 的中位数
    c = [0] * n
    s = 0
    for i in range(1, n):
        s += a[i - 1] - avg
        c[i] = s
    c.sort()
    mid = c[n // 2]
    print(sum(abs(x - mid) for x in c))

if __name__ == "__main__":
    main()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 00:48
 * update_at: 2026-10-05 00:48
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

typedef long long ll;

ll n;
ll a[MAXN]; // 第 i 个小朋友原有的糖果数（下标从 0 开始）
ll c[MAXN]; // c[i] = sum_{k=0}^{i-1}(a[k] - avg)，即前 i 个人的糖果偏差前缀和，c[0] = 0

void read_input() {
    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
}

void solve() {
    // 先求平均数：总糖果数一定能被 n 整除。
    ll total = 0;
    for (ll i = 0; i < n; i++) {
        total += a[i];
    }
    ll avg = total / n;

    // 设第 1 个人顺时针传给第 n 个人的数量为自由变量 x，
    // 则与下一个人之间的传递量可表示为 x - c[i]，
    // 总代价 = sum |x - c[i]|，取 x 为 c[] 的中位数时最小。
    c[0] = 0;
    for (ll i = 1; i < n; i++) {
        c[i] = c[i - 1] + (a[i - 1] - avg);
    }

    sort(c, c + n);
    ll mid = c[n / 2];

    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        if (c[i] > mid) {
            ans += c[i] - mid;
        } else {
            ans += mid - c[i];
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

• 时间复杂度：计算平均数与前缀和差值数组 $c$ 耗时 $O(n)$；排序 $c$ 耗时 $O(n \log n)$；累加曼哈顿距离耗时 $O(n)$。总时间复杂度为 $O(n \log n)$。在 $n = 10^6$ 时，Python 运行耗时约 $0.2 \sim 0.3$ 秒，完全在时限内。
• 空间复杂度：存储原数组与差值数组 $c$ 占用 $O(n)$ 空间。

总结

环状均分纸牌相比普通链状问题的难点在于闭环带来的流动自由度。通过设定相邻传递量的未知数并列出平衡方程，我们利用前缀和消元将 $n$ 个关联变量统一表达为 $x_1 - c_i$ 的形式，成功将代数求和极值问题转化为数轴绝对值距离之和极小化问题，最终利用中位数贪心高效求得全局最优解。