C/C++每天小练（六）——分金币

C/C++每日小练（六）——分金币

分金币

题目描述：

圆桌旁坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务时求出被转手的金币数量的最小值。比如，n=4，且4个人的金币数量分别为1,2,5,4时，只需转移4枚金币（第3个人给第2个人两枚金币，第2个人和第4个人分别给第1个人一枚金币）即可实现每个人手中的金币数目相等。

输入格式：

输入包含多组数据。每组数据第一行为整数n(n<=1000000)，以下n行每行为一个整数，按逆时针顺序给出每个人拥有的金币数。输入结束标志为文件结束符（EOF）。

输出格式：

对于每组数据，输出被转手金币数量的最小值。输入保证这个值在64位无符号整数范围内。

样例输入：

3

100

100

100

4

1

2

5

4

样例输出：

0

4

解：这道题看起来复杂，实际上只需进行简单的转化即可：

我们假设2号给1号金币、3号给2号、4号给3号、...、n号给n-1号、1号给n号（可以给0枚金币，即代表什么也没给～）。

假设编号为i的人初始有Ai个金币。对于1号来说，他给了4号x1枚金币，还剩A1-x1枚；但因为2号给了他x2枚，所以最后还剩A1-x1+x2枚；设最终每人的金币数均为M，则A1-x1+x2=M；同理可递推，得到：

x2=M-A1+x1=x1-C1（令C1=A1-M，以下同理）；x3=M-A2+x2=2M-A1-A2+x1=x1-C2；x4=x1-C3；... ...

也就是说，分金币问题可以转化成所有xi的绝对值之和最小的问题（即|x1|+|x1-C1|+|x1-C2|+...+|x1-Cn-1|最小～）。

也也就是说，问题变为：给定数轴上的n个点，找出一个到他们的距离之和尽量小的点。

这涉及到数学证明，但即使从直观上我们也能猜出，在”中间“的点所得到的距各点距离和最小～

经过如上分析，写出代码即可～

CODE：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 1000000+10;
long long A[maxn], C[maxn], tot, M;	//A[i]:the number of xi's coins; tot: count of coins; M: the average of all coins

int main()
{
	int n;
	while(scanf("%d", &n) == 1)
	{
		tot = 0;
		for(int i = 1; i <= n; i++) { scanf("%lld", &A[i]); tot += A[i]; }
		M = tot / n;
		C[0] = 0;
		for(int i = 1; i < n; i++) C[i] = C[i-1] + A[i] - M;
		sort(C, C+n);
		long long x1 = C[n/2], ans = 0;
		for(int i = 0; i < n; i++) ans += abs(x1-C[i]);
		printf("%lld\n", ans);
	}
	return 0;
}

运行结果：