UVa 11300 Spreading the Wealth 分金币

时间:2023-03-09 07:09:44
UVa 11300 Spreading the Wealth 分金币

圆桌旁坐着 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 号金币。用 X2 表示 2 号给 1 号的金币数目,以此类推:

Ai – Xi + X i + 1 = M              其中A为原有的金币,M 最终状态每人手中的金币数

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

A1 – X1 + X2  = M   –>  X2 = M – A1 + X1 = X1 – C1   其中 C1 = A1 – M

A1 – X2 + X3  = M   –>  X3 = 2 * M – A2 + X3 = X1 – C2   其中 C2 = A1 + A2 – 2 * M

……

题目的目的就是让所有的 Xi 的绝对值之和最小,而 | Xi – Ci | 的意义是数轴上 Xi 到 Ci 的距离。所以题目转化成了 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: }