wikioi-天梯-普及一等-貪心-1098：均分紙牌

題目描述 Description

有 N 堆紙牌，編号分别為 1，2，…, N。每堆上有若幹張，但紙牌總數必為 N 的倍數。可以在任一堆上取若于張紙牌，然後移動。

　　移牌規則為：在編号為 1 堆上取的紙牌，隻能移到編号為 2 的堆上；在編号為 N 的堆上取的紙牌，隻能移到編号為 N-1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。

　　現在要求找出一種移動方法，用最少的移動次數使每堆上紙牌數都一樣多。

　　例如 N=4，4 堆紙牌數分别為：

　　①　9　②　8　③　17　④　6

　　移動3次可達到目的：

　　從 ③ 取 4 張牌放到 ④ （9 8 13 10） -> 從 ③ 取 3 張牌放到 ②（9 11 10 10）-> 從 ② 取 1 張牌放到①（10 10 10 10）。

輸入描述 Input Description

第一行N（N 堆紙牌，1 <= N <= 100）

第二行A1 A2 … An （N 堆紙牌，每堆紙牌初始數，l<= Ai <=10000）

輸出描述 Output Description

輸出至螢幕。格式為：

所有堆均達到相等時的最少移動次數。‘

樣例輸入 Sample Input

4

9 8 17 6

樣例輸出 Sample Output

3

類型：貪心  難度：1.5

題意：題意比較簡答，不贅述

分析：考慮多了的一道題。

考慮從頭順序周遊到尾，若目前堆的紙牌數多餘平均值，那麼容易處理，隻要把多餘的分給右邊的的牌堆即可（因為是從左向右周遊，算法保證目前牌堆的左側都已經排好，隻需考慮右邊的牌堆即可）；

如果目前紙牌不夠，那麼就要像右邊的牌堆借，如果借了右邊的所有牌，仍達不到平均值，就要向右邊的右邊借，以此類推……然而為了保證移動次數最少，相鄰的牌堆之間不能有兩次同方向的移動，即從i->i+1最多移動一次，若移動兩次則一定不是最優。舉例：牌堆（1,1,10），顯然從10向左移動牌，移動兩次即可，而從左向右周遊時，移動次數為3，即（2,0,10）->（2,6,4）->（4,4,4），有兩次移動都是從第2堆移動到第1堆，是以不是最優。那麼我們從左向右周遊時，怎麼滿足最優呢？即可以允許借牌時出現負數，比如第1位先從第2位借3個，第2位變成-2，再從第3位借6個，即可求出最優步數。

代碼：

#include<iostream>
using namespace std;

int main()
{
    int n,ave=0,a[110];
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        ave += a[i];
    }
    ave/=n;
    int ans = 0;
    for(int i=0; i<n-1; i++)
    {
        if(a[i]!=ave)
        {
            a[i+1] += a[i]-ave;
            ans++;
        }
    }
    
    cout<<ans<<endl;
}