糖果傳遞

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Time Limit:?2000ms ??Memory Limit:?262144KB

?老師準(zhǔn)備了一堆糖果,?恰好n個(gè)小朋友可以分到數(shù)目一樣多的糖果.?老師要n個(gè)小朋友去拿糖果,?然后圍著圓桌坐好,?第1個(gè)小朋友的左邊是第n個(gè)小朋友,?其他第i個(gè)小朋友左邊是第i-1個(gè)小朋友.?大家坐好后,?老師發(fā)現(xiàn),?有些小朋友搶了很多的糖果,?有的小朋友只得到了一點(diǎn)點(diǎn)糖果,?甚至一顆也沒(méi)有L,?設(shè)第i個(gè)小朋友有a_i顆糖果.?小朋友們可以選擇將一些糖果給他左邊的或者右邊的小朋友,?通過(guò)”糖果傳遞”最后使得每個(gè)小朋友得到的糖果數(shù)是一樣多的,?假設(shè)一顆糖果從一個(gè)小朋友傳給另一個(gè)小朋友的代價(jià)是1,?問(wèn)怎樣傳遞使得所耗的總代價(jià)最小.

Input

輸入文件第一行一個(gè)正整數(shù)n,表示小朋友的個(gè)數(shù). 接下來(lái)n行,每行一個(gè)整數(shù)a_i,表示第i個(gè)小朋友得到的糖果的顆數(shù). n<=1000000. a_i>=0,?保證a_i在longint/int范圍內(nèi), a_i的總和在int64/long long范圍內(nèi).

Output

輸出只有一個(gè)數(shù),?表示最小代價(jià).

Sample Input

4 1 2 5 4

Sample Output

4

這是昨天周賽的一道題，當(dāng)時(shí)沒(méi)有做出來(lái)，不過(guò)我認(rèn)為這確實(shí)是一道好題。

這道題目看起來(lái)很復(fù)雜，仔細(xì)分析一下并不是太難。 首先，最終每個(gè)小朋友的糖果數(shù)量可以計(jì)算出來(lái)，等于糖果總數(shù)除以n，用ave表示。 假設(shè)標(biāo)號(hào)為i的小朋友開(kāi)始有Ai顆糖果，Xi表示第i個(gè)小朋友給了第i-1個(gè)小朋友Xi顆糖果，如果Xi<0，說(shuō)明第i-1個(gè)小朋友給了第i個(gè)小朋友Xi顆糖果，X1表示第一個(gè)小朋友給第n個(gè)小朋友的糖果數(shù)量。 所以最后的答案就是ans=|X1| + |X2| + |X3| + ……+ |Xn|。 對(duì)于第一個(gè)小朋友，他給了第n個(gè)小朋友X1顆糖果，還剩A1-X1顆糖果；但因?yàn)榈?個(gè)小朋友給了他X2顆糖果，所以最后還剩A1-X1+X2顆糖果。根據(jù)題意，最后的糖果數(shù)量等于ave，即得到了一個(gè)方程：A1-X1+X2=ave。 同理，對(duì)于第2個(gè)小朋友，有A2-X2+X3=ave。最終，我們可以得到n個(gè)方程，一共有n個(gè)變量，但是因?yàn)閺那皀-1個(gè)方程可以推導(dǎo)出最后一個(gè)方程，所以實(shí)際上只有n-1個(gè)方程是有用的。 盡管無(wú)法直接解出答案，但可以用X1表示出其他的Xi，那么本題就變成了單變量的極值問(wèn)題。 對(duì)于第1個(gè)小朋友，A1-X1+X2=ave ?-> ?X2=ave-A1+X1 = X1-C1(假設(shè)C1=A1-ave，下面類似） 對(duì)于第2個(gè)小朋友，A2-X2+X3=ave ?-> ?X3=ave-A2+X2=2ave-A1-A2-x2+X1=X1-C2 對(duì)于第3個(gè)小朋友，A3-X3+X4=ave ?-> ?X4=ave-A3+X3=3ave-A1-A2-A3+X1=X1-C3 …… 對(duì)于第n個(gè)小朋友，An-Xn+X1=ave。 ? 我們希望Xi的絕對(duì)值之和盡量小，即|X1| + |X1-C1| + |X1-C2| + ……+ |X1-Cn-1|要盡量小。注意到|X1-Ci|的幾何意義是數(shù)軸上的點(diǎn)X1到Ci的距離，所以問(wèn)題變成了：給定數(shù)軸上的n個(gè)點(diǎn)，找出一個(gè)到他們的距離之和盡量小的點(diǎn)，而這個(gè)點(diǎn)就是這些數(shù)中的中位數(shù)，具體證明在此省略，請(qǐng)自己證明。
#include<stdio.h> #include<algorithm> using namespace std; typedef long long LL; const int N = 1000000 + 10; int a[N], c[N]; int main() {int n, i;while(~scanf("%d",&n)){LL sum = 0;for(i = 1; i <= n; i++){scanf("%d",&a[i]);sum += (long long)a[i];}LL ave = sum / n;c[1] = 0;for(i = 2; i <= n; i++)c[i] = c[i-1] + a[i] - ave; sort(c+1,c+n+1);LL ans = 0;int mid = c[n/2+1]; //中位數(shù)for(i = 1; i <= n; i++)ans += abs(c[i] - mid); //距離和printf("%lld\n",ans);}return 0; }

與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的糖果传递 （数学题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。