ZCMU 1019: 分金币

解题思路：

附上刘汝佳老师的解题过程：

首先最终每个人的金币数量可以计算出来，它等于金币总数除以人数n。接下来用M来表示每个人最终拥有的金币数。
　现在假设编号为 i 的人初始有Ai 枚金币，对于1号来说，他给了4号x1枚金币，还剩Ai -x1枚金币；但是2号给了他x2枚金币，所以还剩A1-x1+x2枚金币。所以A1-x1+x2=M。同理对于第2个人，有A2-x2+x3=M。最终得到n个方程，实际上只有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
　　对于第3个人，A3-x3+x4=M → x4=M-A3+x3=3M-A1-A2-A3+x1=x1-C3
　　...
　　对于第n个人，An-xn+x1=M。这是一个多余的等式。
　　我们希望所有xi 的绝对值之和尽量小，即|x1|+|x1-C1|+|x1-C2|+...+|x1-Cn-1|要最小。注意到|x1-Ci|的几何意义是数轴上的点x1到Ci 的距离，所以问题变成了：给定数轴上n个点，找出一个到他们距离之和尽量小的点。
　　而这个点就是中位数，它实在是太优美，太巧妙了，而且不少其他问题也能用的上。

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
long long a[1000005],b[1000005];
int main()
{
   int n,i;
   long long k,sum,t;
   while(~scanf("%d",&n))
   {
       k=0;
       for(i=1;i<=n;i++)
       {
           scanf("%lld",&a[i]);
           k=k+a[i];
       }
       k=k/n;
       b[0]=0;
       for(i=1;i<n;i++)
       {
           b[i]=b[i-1]+a[i]-k;
       }
       sort(b,b+n);
       t=b[n/2];
       sum=0;
       for(i=0;i<n;i++)
       {
           sum=sum+abs(t-b[i]);
       }
       printf("%lld
",sum);
   }
   return 0;
}