均分紙牌。。。以前在做這個(gè)題目的時(shí)候，老師給了思路：就是從第一項(xiàng)開始加，可以讓前i堆平均為止，移動(dòng)次數(shù)就是i-1了！然后繼續(xù)掃描下去！累加移動(dòng)次數(shù)就是所求解！

按照這種思路，我那時(shí)直接寫了代碼完事了，其實(shí)這是很不好的！呵呵。。。雖然我們可以通過參考別人的思路解決問題，但是這我們應(yīng)該更多的學(xué)習(xí)，如何從他人的解題思路里獲得自己解決類似問題的思路，如何產(chǎn)生思路！！！

    解題代碼一（按照老師的思路，我以前寫的）

#include<stdio.h>
int main()
{
    int  n,sum,v,sum1;
    int s[100];
    int i,j;
    int count;
     scanf("%d",&n);
    do{
        sum=0;
        sum1=0;
        v=0;
        j=0;
        count=0;
    for(i=0;i<n;i++)
    {
        scanf("%d",&s[i]);
        sum=sum+s[i];
    }

    v=sum/n;

    for(i=0;i<n;i++)
    {
        sum1=sum1+s[i];
        j=j+1;
        if((sum1%v==0)&&(sum1==v*j))
        {
            count=count+j-1;
            sum1=0;
            j=0;            
        }
    }
      printf("%d\n",count);
       scanf("%d",&n);
    }while(n!=0);
}

      今天，我又搜了一下，到底為啥是這么個(gè)解題思路，這讓我困惑了昨天一個(gè)晚上！！更可悲的是，搜出來這個(gè)題目盡然是小學(xué)生數(shù)奧里得題目。。。

      算了還是直切正題，如果有n堆紙牌要均分（當(dāng)然可以均分成功），我們假設(shè)第一堆有紙牌，其他堆都沒有，那我們只要從第一推開始移動(dòng)（總數(shù)-平均值）張紙牌，一堆堆往下分就解決了，這多好呀，移動(dòng)次數(shù)肯定是最少的。。

      當(dāng)然這只是種假設(shè)，跟多的時(shí)候是，每一堆得紙牌都有幾張，這個(gè)時(shí)候上面這種分法自然不行了，但是上面這種分法給了我們一種最少移動(dòng)的思路，就是每次都把i堆分好了。。思考一下，但是新的問題又出現(xiàn)，不是每一堆都可以通過后一堆給（或者前一堆要）從而達(dá)到平均的，萬一后（前）一堆不夠了怎么辦？

         網(wǎng)上走了一遭，發(fā)現(xiàn)紙牌數(shù)量還可以為負(fù)！一開始我也不理解，牌數(shù)為負(fù)，就跟人可以半個(gè)沒啥兩樣，簡直就是自欺欺人！但是我回家想了下，牌數(shù)為負(fù)，固然是不對(duì)的，但是至少他在傳達(dá)著一種信息，我要牌！！！而且我要的是前i堆牌能夠達(dá)到平均值的數(shù)量，當(dāng)然我們也知道，n堆紙牌是肯定能夠被平分的，就是在說最后肯定有一堆可以滿足前i堆的牌！自然他也會(huì)給他前一堆請(qǐng)求所需的牌，這就跟我前面舉只有第一堆有牌的情況一樣了，只是給的時(shí)候牌數(shù)不同，可見負(fù)牌其實(shí)傳達(dá)的是這種意思，而且移動(dòng)次數(shù)為滿足i~j堆平分的堆數(shù)減一，即移動(dòng)j-i-1次！！！于是我又寫了牌數(shù)可負(fù)的代碼：

解題代碼二如下（牌數(shù)可負(fù)）：

#include<stdio.h>
#include<string.h>
int main()
{
    int  n,sum,v;
    int s[100];
    int i,j;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {
        sum=0;
        v=0;
        j=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&s[i]);
            sum=sum+s[i];
        }

        v=sum/n;

        for(i=0;i<n-1;i++)
        {
            if(s[i]<v)
            {
                s[i+1]=s[i+1]-(v-s[i]);
                j++;
            }
            else if(s[i]>v)
            {
                s[i+1]=s[i+1]+(s[i]-v);
                j++;
            }
        }
       
        
       printf("%d\n",j);
    }
    return 0;
}

寫完后我發(fā)現(xiàn)其實(shí)每次找到可以滿足條件的一堆牌，它都會(huì)把前面的所有堆分好！網(wǎng)上說這是貪心算法，但是我覺得這個(gè)貪心跟動(dòng)態(tài)規(guī)劃差不多，可能還要難，因?yàn)樗趧?dòng)態(tài)規(guī)劃的基礎(chǔ)上，還要分析和總結(jié)。首先，他要找最優(yōu)子結(jié)構(gòu)（這個(gè)最有子結(jié)構(gòu)很隱蔽），在這里找到一個(gè)找到可以給（發(fā)）牌的堆，事實(shí)上，這樣的也就找到了一個(gè)連續(xù)x堆可平分的子結(jié)構(gòu) ！其次，總結(jié)最優(yōu)子結(jié)構(gòu)的性質(zhì)，最后發(fā)現(xiàn)牌數(shù)可以為負(fù)以及意義，然后發(fā)現(xiàn)一堆一堆往下分就是結(jié)果！最后就是老師這樣算了！！！這個(gè)過程其實(shí)很復(fù)雜。。。

 我覺得這樣還不過癮，我又寫了個(gè)這種思路下的分牌結(jié)果輸出程序，其實(shí)也可以計(jì)算移動(dòng)次數(shù)（不過我覺得沒啥必要了！！）

代碼如下：

#include<stdio.h>
#include<string.h>
int temp;
void move(int i,int v,int s[100],int d[100])
{
    if(i<0||d[i]==0)    //i<0,不用解釋了，d[i]==0代表前i堆都分配好了
        return;
    if(d[i]==1)            //從后一堆拿
    {
        printf("從第%d堆紙牌向%d堆紙牌移動(dòng)%d張!\n",i+1,i,v-s[i]);
        move(i-1,v,s,d);    //遞歸
        d[i]=0;                //置零，其實(shí)一次遞歸就可以讓前i堆都分配成功！
    }
    
    else if(d[i]==2)    //給后一堆
    {
        printf("從第%d堆紙牌向%d堆紙牌移動(dòng)%d張!\n",i,i+1,s[i]-v);
        d[i]=0;
    }
}

//處理當(dāng)前i堆函數(shù)。。。其實(shí)我自己也不知道怎么定義這個(gè)函數(shù)才對(duì)
/**//*
參數(shù)說明：
i：當(dāng)前堆
v：平均值
s：堆狀態(tài)序列值
d：記錄分配情況：1代表向后一堆取，2代表向后一堆給，0代表本堆已經(jīng)是平均值了，沒有操作
n：堆數(shù)
*/
void mypow(int i,int v,int s[100],int d[100],int n)
{
    if(i==n)            //前n-1堆分配成功后，第n堆一定是平均值，所以直接返回
        return;
    if(s[i]<v)            //如果本堆小于平均值，就向前一堆去要
    {
         d[i]=1;
         if(s[i+1]-(v-s[i])>=0)        //如果前一堆可以給，就直接移動(dòng),事實(shí)上這次給可以讓前i堆紙牌值全部為平均值
         {
              temp=1;
              move(i,v,s,d);        //移動(dòng)函數(shù)
         }
        s[i+1]=s[i+1]-(v-s[i]);        //第i+1堆狀態(tài)變化
        mypow(i+1,v,s,d,n);            //遞歸求解i+1堆
    }
    else if(s[i]>v)                    //如果本堆大于平均值，就給后一堆
    {
        s[i+1]=s[i+1]+(s[i]-v);
        d[i]=2;
        temp=1;
        move(i,v,s,d);                //這里的move其實(shí)可以直接寫成printf
        mypow(i+1,v,s,d,n);            //遞歸求解i+1堆
    }
    else if(s[i]==v)                //如果本堆等于平均值，當(dāng)然不用移動(dòng)了
    {
        d[i]=0;
        mypow(i+1,v,s,d,n);            //遞歸求解i+1堆
    }
    return;
}
int main()
{
    int n,sum,v;
    int s[100],d[100];
    int i;
    int count;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {
        memset(d,0,sizeof(d));
        sum=0;
        v=0;
        count=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&s[i]);
            sum=sum+s[i];
        }

        v=sum/n;
        temp=0;
        mypow(1,v,s,d,n);
        if(!temp)                //這個(gè)就是不用分配標(biāo)記
            printf("不用移動(dòng)了！\n");
    }
    return 0;
}

運(yùn)行結(jié)果如下：