UVa 11300 - Spreading the Wealth

题目地址

描述

圆桌旁坐着$n$个人,每人有一定数量的的金币,金币数总能被$n$整除。每个人可以给他左右相邻的人一些金币,最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。
每组数据第一行为整数 $n(n\leq 1000000)$,以下 $n$ 行每行为一个整数,按逆时针顺序给出每个人应有的金币数。输入结束标志为 $EOF$。
对于每组数据输出被转手金币的数量的最小值。

分析

首先我们可以先计算出最终每个人手中持有的金币数量 $M$,$M$ 等于总金币数量除以人数 $n$。

假设有 $4$ 个人,按顺序编号为 $1, 2, 3, 4$。假设 $1$ 号给 $2$ 号 $3$ 枚金币,然后 $2$ 号给 $1$ 号 $5$ 枚金币,实际上相当于

$2$ 号给 $1$ 号 $2$ 枚金币,而 $1$ 号什么都没有给 $2$ 号。这样,我们设 $x_{2}$ 表示 $2$ 号给了 $1$ 号多少金币,如果 $x_{2}$ 小于 $0$

说明 $1$ 号给了 $2$ 号 $x_{2}$ 枚金币。

现在假设编号为 $i$ 的人初始有 $A_{1}$ 枚金币。对于 $1$ 号,他给了 $4$ 号 $x_{1}$ 枚金币,还剩 $A_{1} - x_{1}$ 枚金币;又因为 $2$

号给了他 $x_{2}$ 枚金币,所以最终他剩 $A_{1} - x_{1} + x_{2}$ 枚金币。对于剩下的人也是一样的,依次我们可以得到 $n$ 个等

式:

这里我们令 $C_{n} = A_{n} - M$,进行移项变为

第二项是这样子变过来的

第三项同理

其实在实际应用中我们并不需要第 $n$ 个等式,因为这道题目中题到过这是一个环形。

我们希望所有的 $x_{i}$ 的绝对值最小,即 $|x_{1}| + |x_{1} - C_{1}| + |x_{1} - C_{2}| + \cdots + |x_{1} - C_{n - 1}|$ 的绝对值最小。

$ |x_{1} - C_{i}|$ 的几何意义是数轴上点 $x_{1}$ 到 $C_{i}$ 的距离。至此问题就变为了给定数轴上的 $n$ 个点,找出一个到

它们距离之和尽量小的点

这里我们简要的证明一下,为什么最优的的 $x_{1}$ 是这些数的中位数。
如图,

任意找一个点,如图中灰色的圆,它左边有 $4$ 个输入点,右边有 $2$ 个输入点。当灰色的圆向左平移 $d$ 个单位,灰

点左边的 $4$ 个点到它的距离距离各减少了 $d$,而灰点右边的 $2$ 个点各增加了 $d$,总共距离减少了 $2d$。当灰点右边

有 $4$ 个点左边有 $2$ 个点的时候,同理,将灰点向右平移 $d$ 个单位长度,距离减少 $2d$。

所以如果输入点的个数有奇数个,则灰点必定会与中间的那个点重合,即为中位数;当个数为偶数,那么灰点可以

位于中间的两个点之间的任意位置,仍然是中位数

有许多题目中,我们转化为这个模型后,都可以用中位数进行求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MAX = 1000000 + 3;
int n;
LL A[MAX];
LL C[MAX];

int main()
{
#ifndef DEBUG
//freopen("test.in","r",stdin);
#endif
while(scanf("%d", &n) != EOF){
LL sum = 0;
for(int i = 0; i < n; i++){
scanf("%lld", &A[i]);
sum += A[i];
}
LL M = sum / n;

C[0] = 0;
for(int i = 1; i < n; i++)
C[i] = C[i - 1] + A[i] - M;
sort(C, C + n);

LL x1 = C[n/2], ans = 0;
for(int i = 0; i < n; i++)
ans += abs(x1 - C[i]);
printf("%lld\n", ans);
}
return 0;
}

其实代码还可以进一步优化,如运用快速选择,在线性时间内求出中位数。
(^∀^●)ノシ

Partager