本文主要是介绍Math - Uva 11300 Spreading the Wealth，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Spreading the Wealth Problem's Link
----------------------------------------------------------------------------
Mean:
n个人围成一圈，每个人手里有Ai个金币，每个人可以给与他相邻的人一些金币，通过一系列的流转后，最后所有人的金币数相等。问整个过程最少需要流转多少金币？
analyse:
这是一道很有趣的数学题。
假设有4个人，按顺序编号1,2,3,4。假设1号给2号3枚金币，2号给1号5枚金币，这等价于2号给了1号2枚金币。
设：第i个人给了第i-1个人Xi枚金币(X1表示第1个人给第n个人X1枚金币)，初始时每个人的金币数位Ai，最终每个人的金币数为M.
可得一下等式：
- A1-X1+X2=M
- A2-X2+X3=M
- A3-X3+X4=M
- A4-X4+X1=M
根据题意，我们最终要求的是：answer=|X1|+|X2|+|X3|+|X4|.
对上面的四个等式变形（用X1来表示其他等式）:
- X1 = X1
- X2 = M-A1+X1 = X1+C1
- X3 = M-A2+X2 = X1+C1+C2
- X4 = M-A3+X3 = X1+C1+C2+C3
这儿的Ci=M-Ai，这个值是可以求出来的（看作是已知的）。
设D0=0,D1=C1,D2=C1+C2,D3=C1+C2+C3
再对上面的式子进行替换得到：
- X1 = X1+D0
- X2 = X1+D1
- X3 = X1+D2
- X4 = X1+D3
那么：
- answer = |X1|+|X2|+|X3|+|X4|
- = |X1+D0|+|X1+D1|+|X1+D2|+|X1+D3|
注意|a+b|这种形式，这在几何数学里表示的是数轴上a点到b点的距离。
D0,D1,D2,D3可以求出，现在的关键是如何求X1，求出X1后，X2,X3,X4都可以通过X1得出。
|X1+D0|+|X1+D1|+|X1+D2|+|X1+D3|这个式子对应的几何概念就是：数轴上有n个数，找一个数X1出来，使得X1到这n个数的距离之和最小。
到现在，问题就变得简单了，这个概念正是中位数的几何意义。
下面就是求出D[]数组，然后找到D[]的中位数，即X1，最后求出X2,X3,X4，累加即得answer.
Time complexity: O(N)
view code
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main( String [] argv ){
Scanner in = new Scanner( new BufferedInputStream( System . in));
while( in . hasNext ()){
int n = in . nextInt();
int [] a = new int [n ];
Long sum = Long . valueOf( 0);
for( int i = 0; i <n ;++ i ){
a [ i ]= in . nextInt();
sum += a [ i ];
}
int ave =( int)( sum /n);
int [] d = new int [n ];
d [ 0 ]= 0;
for( int i = 1; i <n ;++ i ){
d [ i ]= d [ i - 1 ]+ ave - a [ i ];
}
Arrays . sort( d , 0 ,n);
int mid = d [n / 2 ];
Long ans = Long . valueOf( 0);
for( int i = 0; i <n ;++ i ){
ans += Math . abs( mid - d [ i ]);
}
System . out . println( ans);
}
}
}
这篇关于Math - Uva 11300 Spreading the Wealth的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
