题目描述

有 n 个小朋友坐成一圈，每人有 a[i]个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。

输入格式
第一行输入一个正整数 n，表示小朋友的个数。接下来 n行，每行一个整数 a[i]，表示第i个小朋友初始得到的糖果的颗数。

输出格式
输出一个整数，表示最小代价。

数据范围
1≤n≤1000000,
0≤a[i]≤2×109,

数据保证一定有解。

样例

输入样例：

4
1
2
5
4

输出样例：

4

注意数据范围

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int C[100005];
int a[100005];
int main(int argc, char** argv) {
    int n;
    long long sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    sum+=a[i];
    }
    int a0=sum/n;//平均值 
    for(int i=n;i>=1;i--){
    C[i]=C[i+1]+(a0-a[i]);
    }
    sort(C+1,C+n+1);
    long long res=0;
    int c=C[n/2+1];
    for(int i=1;i<=n;i++){
        res+=abs(C[i]-c);
    }
    printf("%lld",res);
    return 0;
}