思路与算法

令平均数avg=sum(ai)/n，ci为前i个小朋友糖数减avg的累计差，取c0=0，共保留n个前缀值。设环上一条边净流量为z，其余边由守恒确定为z+ci或其相反号，总代价化为Σ|z+ci|。选择ci的中位数med，答案Σ|ci−med|。用nth_element选中位数。

正确性说明

每个人最终净收入为avg−ai，逐点写出流入减流出约束，可得到所有边流量仅剩一个自由整数z。每条边至少支付净流量绝对值；按净流方向安排传递可实现该代价，因为糖果守恒且可先从有余量的点传递。绝对值和的最小点为中位数：往右移动时左侧项增加、右侧项减少，只有两侧数量平衡才不再改善。因此所算是最小总代价。

复杂度

初始化与前缀O(n)，nth_element平均O(n)，汇总O(n)，平均总O(n)，空间O(n)。若改排序则为O(n log n)。

易错点

圆环不是线段，不能直接取固定前缀绝对值和；自由环流量必须优化。总数保证可整除，不可丢糖；n1答案0。前缀和与答案使用64位，修订ai上界下不会溢出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n), c(n);
    long long sum = 0;
    for (auto &x : a) {
        cin >> x;
        sum += x;
    }
    long long avg = sum / n;
    for (int i = 1; i < n; i++)
        c[i] = c[i - 1] + a[i - 1] - avg;
    nth_element(c.begin(), c.begin() + n / 2, c.end());
    long long med = c[n / 2], ans = 0;
    for (auto x : c)
        ans += llabs(x - med);
    cout << ans << '\n';
}