题解 : Spreading the Wealth

地址：https://vjudge.net/problem/UVA-11300

1：题意

A Communist regime is trying to redistribute wealth in a village. They have have decided to sit everyone around a circular table. First, everyone has converted all of their properties to coins of equal value, such that the total number of coins is divisible by the number of people in the village. Finally, each person gives a number of coins to the person on his right and a number coins to the person on his left, such that in the end, everyone has the same number of coins. Given the number of coins of each person, compute the minimum number of coins that must be transferred using this method so that everyone has the same number of coins.

大致意思是：初始n个人围坐成环形，每个人都有$a_i$金币。每个人可以给他的左或右边的人一些金币。要求所有人有相同数量的金币，求最小的转手金币的数量，保证金币的总数可以整除人数。

2：思路：

设$x_i$为第i个人向右边的人传递的金币数量，若$x_{i-1}$为负则表示第i个人向左传递金币。最终结果即为$\sum |x_i|$。很显然，我们知道每个人最终的金币数量为金币的平均数设为m。对于任意一个人而言，他最终的金币数$m=a_i+x_{i-1}-x_i$即$x_i=a_i+x_{i-1}-m$每个$x_i$均可以由$x_1$递推求得。结果可表示为$x_i=x_1-c_i$ 所求答案即为$\sum |x_1-c_i|$ 。这个式子的几何意义为在一维坐标轴上点$x_1$到点$c_i$的距离和。我们要最小化这个距离和。那么$x_1$应该取$c_i$的中位数。递推求解$x_i$即可得到答案。

3：代码

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

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1e6+7;
long long a[MAXN],c[MAXN];
inline long long Abs(const long long a){
	return a<0?-a:a; 
}
int main(){
	int n;
	while(scanf("%d",&n)==1){
		long long sum=0,ans=0;
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]); 
			sum+=a[i];
		}
		long long m=sum/n;
		for(int i=1;i<=n;i++){
			c[i]=c[i-1]+a[i]-m;
		}
		sort(c+1,c+n+1);
		long long x1=c[n/2];
		for(int i=1;i<=n;i++){
			ans+=Abs(c[i]-x1);
		}
		cout<<ans<<'\n';
	}
	return 0;
}