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

一.問題描述　

　　亞洲微軟研究院所在的希格瑪大廈一共有6部電梯。在高峰時間，每層都有人上下，電梯每層都停。實習生小飛常常會被每層都停的電梯弄的很不耐煩，于是他提出了這樣一個辦法： 由于樓層并不算太高，那麼在繁忙的上下班時間，每次電梯從一層往上走時，我們隻允許電梯停在其中的某一層。所有乘客從一樓上電梯，到達某層後，電梯停下來，所有乘客再從這裡爬樓梯到自己的目的層。在一樓的時候，每個乘客選擇自己的目的層，電梯則計算出應停的樓層。

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

二.算法描述　　

　　方法一：暴力枚舉，時間複雜度O(N^2)

　　

　　方法二：書上提供的O(N)的動态規劃的算法。

　　假設電梯停在i層樓，可以計算出所有乘客要爬樓層的層數為Y,假設此時有N1個乘客在i層樓以下，N2個乘客在I層樓，N3個乘客在I層樓以上，則當電梯停在i+1層的時候，N1+N2個乘客要多下一層樓，共多下N1+N2層，N3個乘客要少往上面爬一層樓，少上N3層樓，此時Y(i+1) = Y(i) + N1+N2-N3，很顯然，當N1+N2<N3的時候，Y不斷減小。Y1很容易算出來，另外我們還可以看出，N1+N2是遞增的，N3是遞減的，是以N1+N2一旦大于N3的時候，我們直接退出循環即可，沒有必要再計算下去了。

　　方法三：中位數

　　其實這道題目仔細分析起來就是求一組資料的中位數而已。假設兩人，分别到3層樓和8層樓下，在3和8之間取一點，使得到兩個點距離最小，很顯然，在3和8中的每一點到3和8的距離之和都是相等的。推廣到2 3

5 5 6 7 8 8 9這樣一組資料，ans為中位數。

三.結束語　

　　擴充問題:往上爬一層要耗費K個機關的能量，往下走耗費1個機關的能亮，隻需要計算N1+N2-N3變成N1+N2-N3*K即可。其餘的都是一樣的。

　　擴充問題:2個有序數組求合并後的中位數，貌似是算法導論上的，有空再寫……

　　 你讓我安心什麼什麼，說話卻吞吞吐吐，豈非存心讓我不安