形式化题目

$n$ 个小朋友坐成一个环，第 $i$ 人有 $a_i$ 颗糖果。每次操作可以让某个人给相邻（左或右）的人传 1 颗糖果，代价为 1。保证 $\sum a_i$ 能被 $n$ 整除，求使所有人糖果数相等的最小总代价。

$1 \leqslant n \leqslant 10^6$。

正解

思路

朴素做法及其瓶颈

最直接的想法是贪心地模拟传递：每次找一对"多的人"和"少的人"，沿环上较短方向传糖果。但"较短方向"在环上与整体流量耦合——一个人的糖果可能绕圈流过多个中转者，每一步局部选择都影响后面的流向，模拟既难写对又容易陷入 $O(n^2)$ 甚至更高的复杂度，$n \leqslant 10^6$ 完全不可行。

关键转化：只数"经过的糖果"，不模拟过程

无论传递如何进行，最终每人手里都是平均数 $s = \frac{1}{n}\sum a_i$。定义 $x_i$ 为第 $i-1$ 个人（沿环逆时针）净传给第 $i$ 个人的糖果数：$x_i > 0$ 表示 $i-1$ 传给 $i$，$x_i < 0$ 表示 $i$ 反向传给 $i-1$。一次跨越 $k$ 条边的传递可以拆成 $k$ 次相邻传递，代价相同，所以只需统计每条边上净流过多少颗糖果。

第 $i$ 个人的糖果守恒：收到 $x_i$，送出 $x_{i+1}$，初始 $a_i$，最终 $s$，于是

这是一个递推式：整条环的流量只由自由变量 $x_1$（第 $n$ 人给第 $1$ 人的净流量）决定。令 $c_0 = 0$，$c_i = c_{i-1} + a_i - s$（即 $a_i - s$ 的前缀和），逐层代入得

注意到 $c_n = \sum a_i - ns = 0 = c_0$，所以集合 $\{c_0, c_1, \dots, c_{n-1}\}$ 与 $\{c_1, \dots, c_n\}$ 恰好相同，总代价为各边净流量的绝对值之和：

问题变成：在数轴上选一个点 $-x_1$，最小化它到 $n$ 个点 $c_1, \dots, c_n$ 的距离之和——经典的中位数问题。$-x_1$ 取 $c$ 的中位数时代价最小；任何合法传递方案都对应某个 $x_1$，反之取中位数得到的流量也自动满足守恒方程，因此这个下界可以取到。

用样例验证

以样例 $a = [1, 2, 5, 4]$ 为例，$s = 3$：

排序后中位数在 $-2$ 与 $-1$ 之间，任取 $x_1 = 2$，代入 $x_{i+1} = x_1 + c_i$ 得各边净流量

即 4 号给 1 号 2 颗，3 号给 2 号、3 号给 4 号各 1 颗（负号表示反向），总代价 $2+0+1+1 = 4$，与样例输出一致。逐人验证（收到 $x_i$、送出 $x_{i+1}$）：$1+2-0=3$、$2+0-(-1)=3$、$5+(-1)-1=3$、$4+1-2=3$，全部等于平均数 3。有 5 颗糖的 3 号把糖果沿环向两侧分流，各边流量绝对值之和恰好是各点 $c_i$ 到中位数的距离。

于是算法只有三步：求 $s$、做一遍前缀和得到 $c$、排序取中位数求绝对值和。$n = 10^6$ 时排序是主要开销，完全可接受。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15import sys

def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]
    s = sum(a) // n                       # 目标：每人最终 s 颗
    from itertools import accumulate
    # c[i] = a[i]-s + c[i-1]：即 i-1 传给 i 的净糖果数（负表示反向传）
    c = list(accumulate(x - s for x in a))
    c.sort()                              # 代价 = Σ|c[i]-x|，x 取中位数最优
    m = c[n // 2]
    print(sum(abs(v - m) for v in c))

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/**
 * 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-06 14:42
 * update_at: 2026-10-06 14:42
 */

// 糖果传递：环上均分糖果，最小化相邻传递总代价。
// 设 c[i] 为前 i 个人的 (a[i]-s) 前缀和，即第 i 人传给第 i+1 人的净流量
//（负号表示反向传），总代价 = Σ|c[i] - x|，x 取 c 的中位数时最小。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

typedef long long ll;

ll n;
ll a[MAXN]; // a[i]：第 i 个小朋友的初始糖果数
ll c[MAXN]; // c[i]：(a[i]-s) 的前缀和，即边上净流量关于 x_1 的偏移

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

    cin >> n;
    ll sum = 0;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    ll s = sum / n; // 最终每人手里的糖果数（数据保证有解，即 n 整除 sum）

    // 前缀和：c[i] = c[i-1] + a[i] - s，第 n 项恰好回到 0（环闭合）
    for (ll i = 1; i <= n; i++) {
        c[i] = c[i - 1] + a[i] - s;
    }

    // 总代价 = Σ|c[i] + x_1|，数轴上选 -x_1 到各点距离和最小 -> 取中位数
    sort(c + 1, c + n + 1);
    ll mid = c[(n + 1) / 2]; // 中位数（n 为奇数取正中，偶数取任意一个皆最优）

    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        ans += llabs(c[i] - mid);
    }
    cout << ans << endl;

    return 0;
}

复杂度

• 时间复杂度 $O(n \log n)$：一遍前缀和 $O(n)$，排序 $O(n \log n)$（也可用 nth_element 类思想做到期望 $O(n)$）。
• 空间复杂度 $O(n)$：存储数组 $a$ 和前缀和数组 $c$。

总结

• 环上均分问题不要模拟传递过程，而是给每条边设净流量变量 $x_i$，用守恒方程 $x_{i+1} = x_i + a_i - s$ 把所有流量表示成 $x_1$ 的线性函数。
• 代数变形后总代价是 $\sum |c_i + x_1|$，其中 $c_i$ 是 $a_i - s$ 的前缀和——环问题就此变成数轴上的"选一点到各点距离和最小"，即中位数贪心。
• 三个可复用的套路：把长距离传递拆成相邻传递（代价不变）、环上流量只有一个自由变量、绝对值和的最优解在中位数。