1.8 小飛的電梯調度算法

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

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

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

分析與解法

該問題本質上是一個優化問題。首先為這個問題找到一個合適的抽象模型。從問題中可以看出，有兩個因素會影響到最后的結果：乘客的數目及需要停的目的樓層。因此，我們可以從統計到達各層的乘客數目開始分析。

假設樓層總共有N層，電梯停在第x層，要去第i層的乘客數目總數為Tot[i]，這樣，所爬樓梯的總數就是。

因此，我們就是要找到一個整數x，使得的值最小。

解法一

首先考慮簡單解法。

可以從第1層開始枚舉x一直到第N層，然后再計算出如果電梯在第x層樓停的話，所有乘客總共要爬多少層樓。這是最為直接的一個解法。

可以看出，這個算法需要兩重循環來完成計算（偽代碼如清單1-1所示）。

代碼清單1-11

    int nPerson[];       // nPerson[i]表示到第i層的乘客數目
    int nFloor, nMinFloor, nTargetFloor;
    nTargetFloor=-1;
    for(i=1; i <=N; i++)
    {
        nFloor=0;
        for(j=1; j<i; j++)
            nFloor+=nPerson[j] * (i - j);
        for(j=i+1; j <=N; j++)
            nFloor+=nPerson[j] *(j - i);
        if(nTargetFloor==-1 || nMinFloor > nFloor)
        {
            nMinFloor=nFloor;
            nTargetFloor=i;
        }
    }
    return(nTargetFloor, nMinFloor);

這個基本解法的時間復雜度為O（N2）。

解法二

我們希望盡可能地減少算法的時間復雜度。那么，是否有可能在低于O（N2）的規模下求出這個問題的解呢？

我們可以進一步地分析。

假設電梯停在第i層樓，顯然我們可以計算出所有乘客總共要爬樓梯的層數Y。如果有N1個乘客目的樓層在第i層樓以下，有N2個乘客在第i層樓，還有N3個乘客在第i層樓以上。這個時候，如果電梯改停在i-1層，所有目的地在第i層及以上的乘客都需要多爬1層，總共需要多爬N2+N3層，而所有目的地在第i-1層及以下的乘客可以少爬1層，總共可以少爬N1層。因此，乘客總共需要爬的層數為Y-N1+（N2+N3）=Y-（N1-N2-N3）層。

反之，如果電梯在i+1層停，那么乘客總共需要爬的層數為Y+（N1+N2-N3）層。由此可見，當N1>N2+N3時，電梯在第i-1層樓停更好，乘客走的樓層數減少（N1-N2-N3）；而當N1+N2<N3時，電梯在i+1層停更好；其他情況下，電梯停在第i層最好。

根據這個規律，我們從第一層開始考察，計算各位乘客需要爬樓梯的數目。然后再根據上面的策略進行調整，直到找到最佳樓層。總的時間復雜度將降為O（N），代碼如清單1-12所示。

代碼清單1-12

    int nPerson[];       // nPerson[i]表示到第i層的乘客數目
    int nMinFloor, nTargetFloor;
    int N1, N2, N3;
    nTargetFloor=1;
    nMinFloor=0;
    for(N1=0, N2=nPerson[1], N3=0, i=2; i <=N; i++)
    {
        N3+=nPerson[i];
        nMinFloor+=nPerson[i] * (i -1);
    }
    for(i=2; i <=N; i++)
    {
        if(N1+N2<N3)
        {
            nTargetFloor=i;
            nMinFloor+=(N1+N2- N3);
            N1+=N2;
            N2=nPerson[i];
            N3-=nPerson[i];
        }
        else
            break;
    }
    return(nTargetFloor, nMinFloor);

擴展問題

1．往上爬樓梯，總是比往下走要累的。假設往上爬一個樓層，要耗費k單位的能量，而往下走只需要耗費1單位的能量，那么如果題目條件改為讓所有人消耗的能量最少，這個問題怎么解決呢？

這個問題可以用類似上面的分析方法來解答，因此筆者不再贅述，留給讀者自行解決。

2．在一個高樓里面，電梯只在某一個樓層停，這個政策還是不太人性化。如果電梯會在k個樓層停呢？讀者可以發揮自己的想象力，看看如何尋找最優方案。