acwing122. 糖果传递

题目

有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 1。

求使所有人获得均等糖果的最小代价。

题解

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int n;
LL a[N],c[N];


int main(){
    cin>>n;
    LL sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    LL b=sum/n;;
    for(int i=2;i<=n;i++){
        c[i]=c[i-1]+a[i]-b;
    }
    LL ans=0;
    sort(c+1,c+n+1);
    for(int i=1;i<=n;i++){
        ans+=abs(c[i]-c[n+1>>1]);
    }
    cout<<ans<<endl;
    return 0;
}