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

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

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

题意：圆桌坐着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.cnblogs.com/Lour688/p/12666154.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有