[貪心策略]NOIP2009模擬題：貨物搬運 move

天地無情人有情，一方有難八方支援！目前災區最緊缺的就是救災帳篷，全國各地支援的帳篷正緊急向災區運送。假設圍繞汶川縣有環行排列的 n 個救災帳篷的存儲點，每個存儲點存有帳篷數量分別是 M1 ， M2 ，…， Mn ，且 S=M1+M2+ … +Mn 必爲 n 的倍數。可以在任意一個存儲點中任取任意數量的帳篷搬運到相鄰的存儲點。

現在需要找到一種搬運方法，搬運最少的帳篷使得每個存儲點中的帳篷數目相同。

例如： n=5 ，每個存儲點帳篷的數量分別爲 17 ， 9 ， 14 ， 16 ， 4 。我們進行如下搬運：

（1） 存儲點①向存儲點②搬運 1 個帳篷；

（2） 存儲點①向存儲點⑤搬運 4 個帳篷；

（3） 存儲點③向存儲點②搬運 2 個帳篷；

（4） 存儲點④向存儲點⑤搬運 4 個帳篷。

搬運帳篷的總數量是 1+4+2+4=11 ，並且可以證明這樣的搬運方法是最佳搬運方法。

【 輸入文件 】

第一 行一個整數 n （ n ≤ 10000 ），表示有 n

儲存點；第二行 n 個整數（ integer 範圍）

表示 n 個存儲點中帳篷數量。

【 輸出文件 】

一個整數，表示最少搬運的帳篷數量。

【 樣例輸入 】

5

17 9 14 16 4

【 樣例輸出 】

11

 【分析】

大家都做過NOIP2002第二題——均分紙牌吧。這個題就是“均分紙牌”的變形，因為這是個環，可以參照USACO 1.1中的Broken Necklace這個題，把原數組複製一遍，然後每次從中取出長度為N的數組，進行一次“均分紙牌”。詳細請看網上均分紙牌的解題報告。一共N次，找出這N次中的最小移動次數，輸出這個數即可。

注意：C++中要用long long數據類型。

【我的代碼】

#include <iostream>
#include <cstdio>
using namespace std;

int absint(int a)
{
    if(a<0)
        return -a;
    else
        return a;
}

long long N,avg,ans;


int main()
{
    long long S[20001];
    long long T[20001];
    int i;
    freopen("move.in","r",stdin);
    freopen("move.out","w",stdout);
    cin>>N;
   
    for (i=1;i<=N;i++)
    {
        cin >> S[i];
        avg+=S[i];
    }
    avg/=N;
   
    for (int i=1;i<=N;i++)
    {
        S[i+N]=S[i];
    }       
    long long Max=0x7fffffff;
    long long tmp;
    for (int j=1;j<=N;j++)
    {
        ans=0;
        for (int i=j;i<=N+j;i++)
        {
            T[i-j+1]=S[i];
        }
       
        for (int i=1;i<=N;i++)
        {
            if (T[i]!=avg)
            {
                tmp=T[i]-avg;
                T[i+1]+=tmp;
                T[i]=avg;
                ans+=absint(tmp);
            }
        }
        if(ans<Max)
            Max=ans;
    }
    cout<<Max<<endl;
    return 0;
}