记录编号	100026	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 负载平衡	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-05-02 20:06:38	内存使用	0.28 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;

vector <short> a,s;
short n;
short ave = 0;

inline short getshort(){
	char ch;
	short x = 0;
	while (!isdigit(ch = getchar()));
	x = ch - 48;
	while (isdigit(ch = getchar())) x = x * 10 + ch - 48;
	return x;
}
int main(){
	freopen("overload.in","r",stdin);
	freopen("overload.out","w",stdout);
	n = getshort();
	a.push_back(0);
	short x;
	for (short i = 1; i <= n; i ++){
		x = getshort();
		a.push_back(x);
		ave += x;
	}
	ave /= n;
	s.push_back(0);
	for (short i = 1; i < n; i++){
		s.push_back(s.at(i - 1) + a.at(i) - ave);
	}
	sort(s.begin()+1,s.end());
	short mid = s.at(n >> 1);
	short ans = abs(mid);
	for (short i = 1; i < n; i++)
		ans += abs(s.at(i) - mid);
	printf("%d\n",ans);
	return 0;
}