记录编号	232772	评测结果	WWWWWWWWWW
题目名称	[UVa 11300]分金币	最终得分	0
用户昵称	NVIDIA	是否通过	未通过
代码语言	C++	运行时间	0.064 s
提交时间	2016-03-03 07:55:28	内存使用	10.89 MiB

/*
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int M=20000+5;
long long A[M],C[M],tot,m;
int main()
{
freopen("Wealth.in","r",stdin);
freopen("Wealth.out","w",stdout);
	int n;
while(scanf("%d",&n)==1)
{
	tot=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&A[i]);
		tot+=A[i];
	}
	m=tot/n;
		C[0]=0;
		for(int i=1;i<n;i++)
			C[i]=C[i-1]+A[i]-m;//递推金币传递，递推C数组
		sort(C,C+n);
		long long x1=C[n/2],ans=0;
		for(int i=0;i<n;i++)ans+=abs(x1-C[i]);
		printf("%lld\n",ans);
}
return 0;
}附有递推貌似my优化
*/
#include<cstdio>
#include<algorithm>
#define LL long long
#define MAXN 1000010UL
using namespace std;
int n;
LL fec[MAXN],x[MAXN];
LL ABS(LL a,LL b){
	a-=b;
	if(a<0) return -a;
	else return a;
}
int main(){
	freopen("Wealth.in","r",stdin);
	freopen("Wealth.out","w",stdout);
	while(scanf("%d",&n)!=EOF){
		LL sum=0;
		for(int i=1;i<=n;i++){
			scanf("%lld",&fec[i]);
			sum+=fec[i];
		}
		x[0]=0;
		sum/=n;
		for(int i=1;i<n;i++){
			x[i]=x[i-1]-sum+fec[i];
		}
		sort(x,x+n);
		LL ans=0;
		LL x1=x[n/2];
		for(int i=0;i<n;i++){
			ans+=ABS(x1,x[i]);
		}
		printf("%lld\n",ans);
	}
}