记录编号	190619	评测结果	AAAAAAAAAA
题目名称	[UVa 11300]分金币	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.092 s
提交时间	2015-10-03 21:23:37	内存使用	7.92 MiB

#include<cstdio>
#include<algorithm>
#define ABS(A) ((A)>0?(A):(-(A)))
int TEMP,EPX,n,o[1000010],c[1000010];
long long ave,ans;
inline int in()
{
	TEMP=0,EPX=getchar();
	while(EPX<48||EPX>57)
		EPX=getchar();
	while(EPX>47&&EPX<58)
		TEMP=(TEMP<<3)+(TEMP<<1)+EPX-48,EPX=getchar();
	return TEMP;
}
int main()
{
	freopen("Wealth.in","r",stdin);
	freopen("Wealth.out","w",stdout);
	while(scanf("%d",&n)==1)
	{
		ans=ave=0;
		for(int i=1;i<=n;++i)
		{
		    o[i]=in();
		    ave+=o[i];
		}
		ave/=n;
		for(int i=1;i<=n;++i)
		    c[i]=c[i-1]+o[i]-ave;
		std::sort(c+1,c+n+1);
		if(n&1)
		    ave=c[(n>>1)+1];
		else
			ave=(c[n>>1]+c[(n>>1)+1])>>1;
		for(int i=1;i<=n;++i)
		    ans+=ABS(ave-c[i]);
		printf("%d\n",ans);
	}
}
/*
这个题最开始我想的方法比较复杂，后来从书中看到一种比较好的处理方法。
大致处理过程如下：
首先我们设置每个人最初拥有的金币数为Ai，它给出的金币数为xi，得到的金币数为x(i+1)，M表示的是最后平均每个人需要得到多少个，则可以得到如下：
对于第1个人，A1-x1+x2=M -> x2=M-A1+x1=x1-C1(规定C1=A1-M)
对于第2个人，A2-x2+x3=M -> x3=M-A2+x2=2M-A1-A2=x1-C1-C2;
对于第3个人，A3-x3+x4=M -> x4=M-A3+x3=3M-A1-A2-A3+x1=x1-C1-C2-C3;
......
所以S=|x1|+|x1-C1|+|x1-C1-C2|+|x1-C1-C2-C3|+...+|x1-C1-C2-...-Cn|;
对于第n个人，An-Xn+X1=M,这是一个多余的等式，并不能给我们更多的信息。
其实从上面我们的处理就可以看出，我们从第一个人和倒数第二个人的参数信息可以看出其实已经对最后一个人的信息进行了处理，所以最后一个方程对我们来说并不能给我们带来更多的信息，
则将问题转化为我们希望所有xi的绝对值之和最小，所以问题就变成了：给定数轴上的n个点，找出一个点到它们的距离之和尽量小的点。
而可以证明的是中位数的点即为我们所需要找的点。
*/