題意：
? ? ? 圓桌旁作者n個人，每個人都有一定數量的金幣，他們每次可以給相鄰的人一枚金幣（可以給多次），問所有人金幣數都相同的話最少要給多少次金幣。


思路：?
? ? ? 這個題目感覺很好，首先我們可以假設每個人都向他前面的人給出了xi的金幣，x1表示1這個人給了n這個人（因為是環）多少金幣，x2表示2給了以多少金幣，xi可以使負數，負數說明是反著給的x2=-4說明是一給了二4枚金幣，這樣我們就可以列出來一些方程組了
，假設M是平均數，Ai表示第i個人的金幣數，那么有


A1-x1+x2=M ?-> ? ? ? ? ? ? ? x2=x1-(A1-M)= x1-C1 ? 設C1=A1-M
A2-x2+x3=M ?->x3 = x2-(A2-M)=x1-C1-(A2-M)= x1-C2 ? 設C2=(A1-M)+(A2-M)
同理 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? x3= x1-C3 ? 設C3= (A1-M)+(A2-M)+(A3-M)
我們用含有A1的式子推出x2，用含有A2的退出x3...所以我們沒有必要用最后一個式子，還有一點就是 x1 = x1 - C0 那么C0=0;
這樣推到之后就變成我們是要求 |x1| + |x1-C1| + |x2-C2|......
那么把他們和一維坐標聯系起來，是不是就是求所有點到x1點（Ci構成的點）的距離和的最小值了，這樣我們只要求出x1就行了，其實這個x1就是所有C的中位數，為什么是這樣這個很好理解，我們可以在紙上畫一畫，比如當前的x1左邊有4個點，右邊有5個點，那么把x1向右移動一小塊距離d(不要跨過右邊的點)我們會發現整體是左邊增加4d，右邊減少5d所以我們要往左移，不能往右移，最后奇數的情況就是中間的那個數最優（中位數），偶數的時候是中間的那兩個之間的位置（包括中間的那兩個）的區間都是最優的，還可以用中位數表示。



#include<stdio.h>
#include<algorithm>


#define N 1000000 + 10


using namespace std;


long long num[N];
long long C[N];


long long abss(long long x)
{
? ?return x > 0 ? x : -x;
}?


int main ()
{
? ?int n ,i;
? ?long long Ans ,Sum ,M;
? ?while(~scanf("%d" ,&n))
? ?{
? ? ? for(Sum = 0 ,i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%lld" ,&num[i]);
? ? ? ? ?Sum += num[i];
? ? ? }
? ? ? M = Sum / n;
? ? ? C[0] = 0;
? ? ? for(i = 1 ;i < n ;i ++)
? ? ? C[i] = C[i-1] + num[i] - M;
? ? ? sort(C ,C + n);
? ? ? long long x1 = C[n/2];
? ? ? for(Ans = 0 ,i = 0 ;i < n ;i ++)
? ? ? Ans += abss(x1 - C[i]);
? ? ? printf("%lld\n" ,Ans);
? ?}
? ?return 0;
}
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ? ??
? ?
?

總結

以上是生活随笔為你收集整理的UVA11300分金币的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。