记录编号	34300	评测结果	AAAAAAAAAA
题目名称	货物搬运	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	1.313 s
提交时间	2011-12-08 21:11:53	内存使用	0.57 MiB

#include <fstream>
using namespace std;
ifstream fin("move.in");
ofstream fout("move.out");
long long n,A[20001],Ave,Min=2000000000;
long long D[20001];
int main()
{
	fin>>n;
	for(int i=1;i<=n;i++)
	{
		fin>>A[i];
		A[i+n]=A[i];
		Ave+=A[i];
	}
	Ave/=n;
	for(int i=1;i<=n;i++)
	{
		D[i]=A[i]-Ave;
		D[i+n]=D[i];
	}
int i,j;
	for(i=1 ; i<n ; i++)
	{
		long long SD=i+n,Sum=0,Cost=0;
		for(j=i;j<SD;j++)
		{
			Sum+=D[j];
			Cost+=(Sum>0?Sum:-Sum);
			if(Cost>=Min)
				break;
		}
		if(Cost<=Min)
			Min=Cost;
	}
	fout<<Min<<endl;
	fin.close();
	fout.close();
	return 0;
}