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

       }

   }

}