# 圆桌均分硬币 ——（推导式子）

0
11

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

3

100

100

100

4

1

2

5

4

Sample Output

0

4

• 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|+|x1-C1|+|x1-C2|+……+|x1-C(n-1)|的最小值

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

``` 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 }```

<

0