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.io.BufferedInputStream;

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);

               ans+=Math.abs(mid-d[i]);

           System.out.println(ans);

       }

   }

}