bzoj1045 糖果傳遞

Description

有n個小朋友坐成一圈，每人有ai個糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞一個糖果代價為1。

Input

第一行一個正整數nn<=1'000'000，表示小朋友的個數．

接下來n行，每行一個整數ai，表示第i個小朋友得到的糖果的顆數．

Output

求使所有人獲得均等糖果的最小代價。

Sample Input

4
1
2
5
4

Sample Output

4

這道題讓我想到了白書上面的相似的一道題：

UVA11300 Spreading the Wealth

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.

Input

There is a number of inputs. Each input begins with n (n < 1000001), the number of people in the village. n lines follow, giving the number of coins of each person in the village, in counterclockwise order around the table. The total number of coins will fit inside an unsigned 64 bit integer.

Output

For each input, output the minimum number of coins that must be transferred on a single line.

Sample Input

3

100

100

100

4

1

2

5

4

Sample Output

0

4

題意：ｎ個人圍成一圈，每個人都有一些硬幣，，每個人只能給左右相鄰的人硬幣，問最少交換幾個硬幣，使每個人硬幣一樣多。

我第一反應：費用流。第二反應：費用流。第三反應：費用流。

然后看uva11300題解：

首先，最終每個人金幣數量可以計算出來，我們用M表示每個人最后擁有的金幣數。

我們對于第i個人可以看作他給了他左邊的人x_i個金幣（負數表示反向傳遞），他右邊的人給了他x_i+1個金幣，假設他一開始擁有的金幣數量為A_i，那么有A_i-x_i+x_i+1=M。

如果我們繼續列下去就會變成這樣：

A₁-x₁+x₂=M -> x₂=M-A₁+x₁?-> ?令C₁=A₁-M -> x₂=x₁-C₁

A₂-x₂+x₃=M -> x₃=M-A₂+x₂=2*M-A₁-A₂+x₁ -> ?令C₂=A₁+A₂-2*M -> x₃=x₁-C₂

A₃-x₃+x₄=M -> x₄=M-A₃+x₃=3*M-A₁-A₂-A₃+x₁?-> ?令C₃=A₁+A₂+A₃-3*M?-> x₄=x₁-C₃

.......

那么我們就會得到n個等式，但是我們發現我們可以用這n個等式中的任意n-1個去變換得到最后剩下那個等式。

因為我們知道 $\sum A_i =M \times n $ ，那么最后一個等式C_n=0，就是x₁=x₁。

也就是說，最后那個等式是沒有用的，我們只會用到n-1個等式。那么這n-1個等式可以用來做什么呢，我們怎樣才能求得 $ \sum abs(x_i) $ 最小值呢？

$ \sum abs( x_i ) = abs( x_1 )+abs( x_2 )+abs( x_3 )+......+abs( x_n )=abs( x_1 ) +abs(x_1-C_1) +abs(x_1- C_2)+ ......+abs(x_1-C_{n-1})$

由于C_i是可以直接計算出來的，可以當作常數，所以說這個等式相當于是求一個最優的x₁，使得數軸上x₁到C_i距離和最小，而這個距離和就是我們所求的答案。

最后問題轉化成求數軸上一個點到所有已知的點最小距離，相信在小學（或是初中）數學老師都講過，這樣的點就是中位數啦。

然后就直接算出C，然后算中位數與其他的所有的點的距離。

bzoj1045 代碼：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1e6+10;
long long n,tot,ans,c,A[maxn],C[maxn];long long aa;char cc;
long long read() {aa=0;cc=getchar();while(cc<'0'||cc>'9') cc=getchar();while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();return aa;
}int main() {n=read();for(int i=1;i<=n;++i) A[i]=read(),tot+=A[i];tot/=n;for(int i=1;i<n;++i) C[i]=A[i]-tot+C[i-1];sort(C+1,C+n+1);//還有一個C[i]為0的 for(int i=1;i<=n;++i) ans+=abs(C[i]-C[(n+1)>>1]);printf("%lld",ans);return 0;
}