[HAOI2008] 糖果传递

有 (n) 个人围成一圈，第 (i) 个人有 (a_i) 个球，通过相互传递使得每个人球数均等，传递一人次代价为 (1)，求最小代价。

Solution

设 (c_i = a_i - avg)，即第 (i) 个人的输出量

令 (x_i) 表示 (i) 一共向 (i-1) 传递的个数，那么由 (c_1=x_1-x_2 o x_2=x_1-c_1), (c_2=x_2-x_3=x_1-c_1-x_3 o x_3=x_1-c_1-c_2)

设 (d_i=sum^{i-1} c_i+x_1)，则我们要最小化 (sum_i |d_i-x_1|)

求出 (d) 数列的中位数即可

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

#define int long long
const int N = 1000005;

int n,a[N],b[N],c[N],d[N];

signed main() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int avg=0;
    for(int i=1;i<=n;i++) avg+=a[i];
    avg/=n;
    for(int i=1;i<=n;i++) c[i]=a[i]-avg;
    for(int i=1;i<=n;i++) d[i]=d[i-1]+c[i];
    sort(d,d+n);
    int mid=d[(n-1)/2];
    int ans=0;
    for(int i=0;i<n;i++) ans+=abs(mid-d[i]);
    cout<<ans<<endl;
}