Description
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。
Input
小朋友个数n，下面n行 ai
Sample Input
4
1 2 5 4
Sample Output
4
思
- 思维难度高的贪心题
- Q:为什么不能像均分纸牌那样做？A:代价！比如1传一圈给n代价为n，但换一个方向后代价就为1
- 现在假设编号为i的人初始有Ai个糖果。对于1号来说，他给了n号x1个糖果，还剩A1-x1个；但是因为2号给了他x2个糖果，所以最后还剩A1-x1+x2个糖果。根据题设，该金币数等于M。换句话说，我们得到了一个方程：A1-x1+x2=M。
同理，对于第2个人，有A2-x2+x3=M。最终，我们可以得到n个方程，一共n个变量，是不是可以直接解方程组了呢？很可惜，还不行。因为从前n-1个方程可以推导出最后一个方程。所以，实际上只有n-1个方程是有用的。
尽管无法直接解出答案，我们还是可以尝试着用x1表示出其他的xi，则本题就变成了单变量的极值问题。
对于第1个人，A1-x1+x2=M→x2=M-A1+x1=x1-C1(令C1=A1-M，下面类似)
对于第2个人，A2-x2+x3=M→x3=M-A2+x2=2M-A1-A2+x1=x1-C2（C2=C1+A2-M）
对于第3个人，A3-x3+x4=M→x4=M-A3+x3=3M-A1-A2-A3+x1=x1-C3
.....
对于第1个人，An-xn+x1=M。这是一个多余的等式，并不能给我们更多的信息。
我们希望所有的xi的绝对值之和尽量小，即|x1|+|x1-C1|+|x1-C2|+...+|x1-Cn-1|要最小。注意到|xi-Ci|的集合意思是数轴上点x1到Ci的距离，所以问题变成了：给定数轴上的n个点，找出一个到它们的距离之和尽量小的点。
结论：给定数轴上的n个点，在数轴上的所有点中，中位数离所有顶点的距离之和最小。凡是能转化为这个模型的题目都可以用中位数求解。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 1000005
using namespace std;
int n,a[maxn];
long long c[maxn],sum;
int main()
{
int n; scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
sum/=n;
for(int i=1;i<=n;++i) c[i]+=sum-a[i]+c[i-1];
sort(c+1,c+n+1);
int mid=c[n/2]; long long ans=0;
for(int i=1;i<=n;++i) ans+=abs(mid-c[i]);
printf("%lld",ans);
return 0;
}