假定 1 号给了 2 号 4 枚金币，而 2 号给了 1 号 1 枚金币，这样等同于 1 号给了 2 号 3 枚金币，而 2 号没有给 1 号金币。用 X 表示 2 号给 1 号的金币数目，以此类推：
A – X + X = M 其中A为原有的金币，M 最终状态每人手中的金币数
这样，可以得到 1 ~ n 一共 n 个方程。但是无法用这 n 个方程得出最终答案。不过可以用 X 来表示其他所有的 X 。于是，这道题目变成了求单变量最值的问题。
A – X + X = M –> X = M – A + X= X – C 其中 C = A – M
A – X + X = M –> X = 2 * M – A + X= X – C 其中 C = A + A – 2 * M
……
题目的目的就是让所有的 X 的绝对值之和最小，而 | X – C | 的意义是数轴上 X 到 C 的距离。所以题目转化成了 n 个点到某点的最小距离和为多少。
自然而然的就想到了中位数，于是就找出 C 的中位数，最后一个for循环就能找出答案。
附AC代码：
1: #include <stdio.h>
2: #include <math.h>
3: #include <iostream>
4: #include <cstdarg>
5: #include <algorithm>
6: #include <string.h>
7: #include <stdlib.h>
8: #include <string>
9: #include <list>
10: #include <vector>
11: #include <map>
12: #define LL long long
13: #define M(a) memset(a, 0, sizeof(a))
14: using namespace std;
15:
16: void Clean(int count, ...)
17: {18: va_list arg_ptr;
19: va_start (arg_ptr, count);
20: for (int i = 0; i < count; i++)
21: M(va_arg(arg_ptr, int*));
22: va_end(arg_ptr);
23: }
24:
25: LL c[1000009], a[1000009];
26:
27: int main()
28: {29: int n;
30: while (~scanf("%d", &n)) 31: {32: LL m = 0;
33: for (int i = 0; i < n; i++)
34: { 35: scanf("%d", &a[i]);36: m += a[i];
37: }
38: m /= n;
39: for (int i = 1; i < n; i++)
40: c[i] = c[i - 1] + a[i] - m;
41: sort(c, c + n);
42: LL x1 = c[n / 2];
43: LL res = 0;
44: for (int i = 0; i < n; i++)
45: res += abs(x1 - c[i]);
46: printf("%lld\n", res);47: }
48: return 0;
49: }