Description
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
Input
第一行一个正整数nn<=1'000'000，表示小朋友的个数．
接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．
Output
求使所有人获得均等糖果的最小代价。
Sample Input
4
1
2
5
4
1
2
5
4
Sample Output
4
题解
这道题对于最终小朋友手中的糖的数量我们是可以算出来的，我们用ave来表示
我们假设Gi表示第i个人给第i-1个人糖的数量，G1表示第1个人给第n个人
那么最后答案就是|G1|+|G2|+···+|Gn|
那么到最后
第一个人的糖就是A1-G1+G2=ave
第二个人的糖就是A2-G2+G3=ave
······
第n个人的糖就是An-Gn+G1=ave
这里我们假设Ci=Ci-1+Ai-ave
所以通过第一个人的糖，我们可以推出G2=G1-C1
通过第二个人，可以推出G3=G1-C2
······
第n个人，可以推出Gn=G1-Cn-1
所以最后答案就变成了|G1|+|G1-C1|+|G1-C2|+···+|G1-Cn-1|
对于求最后答案，问题就变成了给你坐标轴上的n个点，要你找到一个点，使得这个点到所有的点的距离之和最小
而这个点的坐标就是坐标轴上点的中位数
#include<bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;
int n,ave;
ll sum,ans;
int a[N],c[N];
int main(){
scanf("%d",&n);
for (int i=;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
ave=sum/n;
for (int i=;i<=n;i++)
c[i]=c[i-]+a[i]-ave;
sort(c+,c++n);
int mid=c[(n>>)+];
for (int i=;i<=n;i++)
ans+=abs(mid-c[i]);
printf("%lld\n",ans);
return ;
}