记录编号	85936	评测结果	AAAAAAAAAA
题目名称	[UVa 11300]分金币	最终得分	100
用户昵称	超级傲娇的AC酱	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2014-01-17 10:04:10	内存使用	20.88 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=1000000+10;
long long A[maxn],B[maxn],C[maxn],sum,M;
int main()
{
	freopen("Wealth.in","r",stdin);
	freopen("Wealth.out","w",stdout);
	int n,i;
	while(scanf("%d",&n)==1)
	{
		sum=0;
		for(i=1;i<=n;i++)
		{
			scanf("%lld",&A[i]);
			sum+=A[i];
		}
		M=sum/n;
		C[0]=0;
		for(i=1;i<n;i++)
			C[i]=C[i-1]+A[i]-M;
		sort(C,C+n);
		long long x1=C[n/2],ans=0;
		for(i=0;i<n;i++)ans+=abs(x1-C[i]);
		printf("%lld\n",ans);
	}
	return 0;
}