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

假定 1 号给了 2 号 4 枚金币，而 2 号给了 1 号 1 枚金币，这样等同于 1 号给了 2 号 3 枚金币，而 2 号没有给 1 号金币。用 X₂ 表示 2 号给 1 号的金币数目，以此类推：

A_i – X_i + X _{i + 1} = M              其中A为原有的金币，M 最终状态每人手中的金币数

这样，可以得到 1 ~ n 一共 n 个方程。但是无法用这 n 个方程得出最终答案。不过可以用 X₁ 来表示其他所有的 X_i 。于是，这道题目变成了求单变量最值的问题。

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_i 的绝对值之和最小，而 | X_i – C_i | 的意义是数轴上 X_i 到 C_i 的距离。所以题目转化成了 n 个点到某点的最小距离和为多少。

自然而然的就想到了中位数，于是就找出 C 的中位数，最后一个for循环就能找出答案。

附AC代码：

1: #include 
      

2: #include 
      

3: #include 
      

4: #include 
      

5: #include 
      

6: #include 
      

7: #include 
      

8: #include 
      

9: #include 
      

10: #include 
      

11: #include 

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: }