圓桌均分硬幣 ——（推導式子）-有解無憂

A Communist regime is trying to redistribute wealth in a village. They have have decided to sit everyonearound 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, eachperson 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 everyonehas the same number of coins.

Input

There is a number of inputs. Each input begins withn(n<1000001), the number of people in thevillage.nlines follow, giving the number of coins of each person in the village, in counterclockwiseorder around the table. The total number of coins will t 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

100

Sample Output

題意：圓桌坐著N個人，每個人有一定的金幣，金幣總數能被N整除，每個人能給左右相鄰的人一些金幣，最終使得每個人的金幣數目相等，求被轉手金幣數量的最小值，

設：

xi表示i號給i-1號xi金幣（若xi為負，這表示i-1號給i號(-xi)個金幣）
Ai表示i號一開始持有的金幣

則：

對與第1個人:A1-X1+X2=M ->（移項） X2=X1-(A1-M)（用x1減是為了最后得出一個距離的式子）;
對于第2個人：A2-X2+X3=M ->x3=x2-(A2-M) -> x3=x1-(A1+A2-2M)；

　　類似的去遞推：

　　xi=x1-(A1+A2+......+A(i-1)-M*(i-1))

　　令C1=A1-M，C2=A1+A2-M*2......Ci=A1+A2+......+Ai-M*i;(每個C都可以求出)

　　所以我們可以把x的整個陣列換成用x1和C表示：

　　x1=x1;

　　x2=x1-C1;

　　一直到 xn=x1-C(n-1);

所以我們的答案應該是 |x1|+|x2|+|x3|+……+|xn|的最小值；

->|x1|+|x1-C1|+|x1-C2|+……+|x1-C(n-1)|的最小值

首項|x1|可以是|x1-0|(我們可以讓C0=0)

->|x1-C0|+|x1-C1|+|x1-C2|+……+|x1-C(n-1)|

故當X1取C陣列的中間值時，結果最小，

注意：|X1 – Ci|在數軸上就是x1到Ci的距離，所以問題變成了：給定數軸上的n個點，找出一個到它們的距離之和盡量小的點，

這個最優的X1就是這些數的“中位數”，即排序以后位于中間的數，

代碼：

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn=1000005;
 7 long long A[maxn],C[maxn],tot,M;
 8 int main()
 9 {
10 //    freopen("1.in","r",stdin);
11        int n;
12        while(scanf("%d",&n)!=EOF){
13        tot=0;
14        for(int i=1;i<=n;i++){
15           scanf("%lld",&A[i]);
16           tot+=A[i];
17        }
18        M=tot/n;//求平均值
19        C[0]=0;
20        for(int i=1;i<n;i++)
21                C[i]=C[i-1]+A[i]-M;//C陣列算出
22            sort(C,C+n);//記得排序
23            long long x1=C[n/2];//x1算出，每人的硬幣移動次數皆可表示
24            long long ans=0;
25            for(int i=0;i<n;i++)
26           ans+=(x1-C[i]>=0?x1-C[i]:C[i]-x1);
27        printf("%lld\n",ans);
28    }
29    return 0;
30 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40782.html

標籤：C++

上一篇：無重復字符的最長子串

下一篇：尋找兩個有序陣列的中位數