分金幣
題目描述：
圓 桌旁坐著n個人，每人有一定數量的金幣，金幣總數能被n整除。每個人可以給他左右相鄰的人一些金幣，最終使得每個人的金幣數目相等。你的任務時求出被轉手 的金幣數量的最小值。比如，n=4，且4個人的金幣數量分別為1,2,5,4時，只需轉移4枚金幣（第3個人給第2個人兩枚金幣，第2個人和第4個人分別 給第1個人一枚金幣）即可實現每個人手中的金幣數目相等。
輸入格式：
輸入包含多組數據。每組數據第一行為整數n(n<=1000000)，以下n行每行為一個整數，按逆時針順序給出每個人擁有的金幣數。輸入結束標志為文件結束符（EOF）。
輸出格式：
對於每組數據，輸出被轉手金幣數量的最小值。輸入保證這個值在64位無符號整數范圍內。
樣例輸入：
3
100
100
100
4
1
2
5
4
樣例輸出：
0
4
解：這道題看起來復雜，實際上只需進行簡單的轉化即可：
我們假設2號給1號金幣、3號給2號、4號給3號、...、n號給n-1號、1號給n號（可以給0枚金幣，即代表什麼也沒給～）。
假設編號為i的人初始有Ai個金幣。對於1號來說，他給了4號x1枚金幣，還剩A1-x1枚；但因為2號給了他x2枚，所以最後還剩A1-x1+x2枚；設最終每人的金幣數均為M，則A1-x1+x2=M；同理可遞推，得到：
x2=M-A1+x1=x1-C1（令C1=A1-M，以下同理）；x3=M-A2+x2=2M-A1-A2+x1=x1-C2；x4=x1-C3；... ...
也就是說，分金幣問題可以轉化成所有xi的絕對值之和最小的問題（即|x1|+|x1-C1|+|x1-C2|+...+|x1-Cn-1|最小～）。
也也就是說，問題變為：給定數軸上的n個點，找出一個到他們的距離之和盡量小的點。
這涉及到數學證明，但即使從直觀上我們也能猜出，在”中間“的點所得到的距各點距離和最小～
經過如上分析，寫出代碼即可～
CODE：
#include<cstdio> #include<algorithm> using namespace std; const int maxn = 1000000+10; long long A[maxn], C[maxn], tot, M; //A[i]:the number of xi's coins; tot: count of coins; M: the average of all coins int main() { int n; while(scanf("%d", &n) == 1) { tot = 0; for(int i = 1; i <= n; i++) { scanf("%lld", &A[i]); tot += A[i]; } M = tot / n; C[0] = 0; for(int i = 1; i < n; i++) C[i] = C[i-1] + A[i] - M; sort(C, C+n); long long x1 = C[n/2], ans = 0; for(int i = 0; i < n; i++) ans += abs(x1-C[i]); printf("%lld\n", ans); } return 0; }
運行結果：
