UVa11300

/* 代码参照《算法禁赛入门经典训练指南》，已经提交AC 主要修改地方是只使用一个数组 */ #include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int nmax=1000000+5; long long int A[nmax]; int main() { int n; while(scanf("%d",&n)==1){ long long tot=0,M,ans=0; for(int i=0;i<n;++i){ scanf("%lld",&A[i]); tot+=A[i]; } M=tot/n; A[0]-=M; for(int i=1;i<n;++i)A[i]+=(A[i-1]-M); sort(A,A+n); long long int x0=n%2==0?A[n/2]:(A[n/2]+A[n/2+1])/2; for(int i=0;i<n;++i)ans+=abs(A[i]-x0); printf("%lld\n",ans); } return 0; }