《程式設計之美》小飛的電梯排程算法

亞洲微軟研究院所在的希格瑪大廈一共有6部電梯。在高峰時間，每層都有人上下，電梯每層都停。實習生小飛常常會被每層都停的電梯弄的很不耐煩，于是他提出了這樣一個辦法：

由于樓層并不算太高，那麼在繁忙的上下班時間，每次電梯從一層往上走時，我們隻允許電梯停在其中的某一層。所有乘客從一樓上電梯，到達某層後，電梯停下來，所有乘客再從這裡爬樓梯到自己的目的層。在一樓的時候，每個乘客選擇自己的目的層，電梯則計算出應停的樓層。

問：電梯停在哪一層樓，能夠保證這次乘坐電梯的所有乘客爬樓梯的層數之和最少？

解法一：暴力枚舉法。從第1層枚舉到第N層，求出電梯在x層停的話，所有乘客需要怕多少層樓。求出最少的那層即可。代碼略。

解法二：動态規劃。假設電梯停在第x層，已知目的樓層在x層的有N2人，在x層以下的有N1人，在x層以上的有N3人。此時總花費為sum。則往上走一層的話，總花費變為sum + N2 + N1 - N3。那麼初始狀态電梯停在第一層，向上進行狀态的變遷，開始時N2 + N1 - N3 < 0。sum越來越小，直到某一層N2 + N1 >= N3，就沒有必要在往上走了。這時已求出最合适的樓層了。

解法三：我的方法。哈哈。其實沒有那麼複雜。假設隻有兩個人，一個去9層，一個去2層，那麼不管電梯停在2至9層中間的任何樓層，兩個人的總花費都是7.就比如在數軸上點2和點9中間的任何點距離2和9的距離之後都是7。那麼停在哪都無所謂了。接着我們擴充開來，假設有N個人，他們的目标樓層分别是2,3,3,4,5,5,5,7,7,8,9。按我們的想法，對于兩端的（2,9）電梯隻要停在他們之間都一樣。同理對于（3,8）電梯隻要停在他們中間都一樣……。最終電梯隻要停在中間那個數即可。也就是中位數。原來弄半天隻需求出中位數即可啊。如果N是偶數個的話，停在中間那兩個數任何一個都可以的。歡迎大家對我的解法拍磚。代碼就不用了吧。

擴充問題的解法：

如果往上爬樓梯比較累，往下走較容易，假設往上走一層耗費k機關的能量，往下走一層隻耗費1機關的能量。此時就不适合用我的解法三了，解法二更加适合。代碼如下：

int controlElevator(int nPerson[], int nfloor, int upWeight){
    int targetFloor = ;
    int minFloor = ;
    int N1 = ;
    int N2 = nPerson[];
    int N3 = ;
    int i = ;
    for(i = ; i <= nfloor; i++){ //i表示大衆意義上的第i層
        N3 += nPerson[i];
        minFloor += (nPerson[i] * (i - ) * upWeight);
    }
    for(i = ; i <= nfloor; i++){
        if(N1 + N2 < N3 * upWeight){
            minFloor += (N1 + N2 - N3 * upWeight);
            N3 -= nPerson[i];
            N1 += N2;
            N2 = nPerson[i];
            targetFloor = i;
        }
        else
            break;
    }
    return minFloor;
//  return targetFloor;
}
           

下面附上我的解法三的代碼：

int main(){ 
    int nPerson[]={,,,,,,,,};
    int left=, right=;
    while(right-left > ){
        while(nPerson[left] == )
            ++left;
        nPerson[left]--;
        while(nPerson[right] == ){
            if(right < left)
                break;
            --right;
        }           
        nPerson[right]--;
    }
    cout<<left+<<endl; 
    return ;
}