[BZOJ1045][HAOI2008] 糖果传递[贪心,中位数]

#include<cstdio>
#include<algorithm>
#define re register
#define in inline
#define int long long
using namespace std;
in int read()
{
	int s(0),b(0);char ch;
	do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	if(b) return -s;
	return s;
}
int n,s[1000010],d[1000010],av,mid,ans;
signed main()
{
	n=read();
	for(re int i=1;i<=n;++i) s[i]=read(),s[i]+=s[i-1];
	av=s[n]/n;
	for(re int i=1;i<=n;++i) d[i]=s[i]-i*av;
	sort(d+1,d+n+1);
	if(n&1) mid=d[n/2+1];
	else mid=(d[n/2]+d[n/2+1])/2;
	for(re int i=1;i<=n;++i) ans=ans+abs(d[i]-mid);
	printf("%lld\n",ans);
	return 0;
}