編程之美-電梯調(diào)度算法
一問題描述：
所有的員工均在1樓進電梯的時候，選擇所要到達的樓層。
然后計算出停靠的樓層i，當(dāng)?shù)竭_樓層i的時候，電梯停止。
所有人走出電梯，步行到所在的樓層中。
求所有人爬的樓層數(shù)目和的最小值。
二 問題解決方法：
二 解決方案：
(1)使用簡單的方法，直接將樓層從1到n開始遍歷
sum(person[i] * |i - j| ) 此表達式為一個雙重循環(huán)，i與j均為1-n的循環(huán)。
j下標(biāo)表示電梯停靠的樓層。
person數(shù)組表示，對應(yīng)i層的下電梯的人數(shù)。此算法負(fù)責(zé)度為o(n*n)
對應(yīng)的j是上述和為最小的一層即為所求。 上面的算法復(fù)雜度為o(n)
(2)下面考慮一個簡單的算法，使其復(fù)雜度達到o(n)
考慮假如電梯停靠在某一樓層i處，假設(shè)在i處下樓的客人為N2,
在i以上樓層的客人數(shù)目為N3 ，在i一下樓層的客人數(shù)目為N1。
且將電梯在i層停止時，全部人員的路程之和記為T。
那么加入電梯在i-1層停的話，則原來i層之上的人需要多爬一層，即增加了N3
第i層的人需要多爬一層，則結(jié)果增加了N2, i層之下的人則少爬了一層，結(jié)果減去N1
所以第i-1層的結(jié)果為 T - N1 + N2 + N3 。即結(jié)果可以即為 T -(N1 - N2 - N3)
下面考慮在i+1層的結(jié)果，若電梯在i+1層停止的話，原來i層之上的客戶都會少爬一層，
則結(jié)果減少N3 ，而i層之下的人員則都會多爬一層即增加了N1 ，第i層的人員都會多爬一層
即為增加了N2 。則結(jié)果為 T + N1 + N2 - N3
綜上我們得出，
(1)若N1 > N2 + N3的時候， 我們在第i-1層 選擇電梯停止最好。
(2)若N1 + N2 < N3的時候， 我們選擇在第i+1層停止電梯最好。
下面我們可以先計算出來當(dāng)i=1時候的T ，然后判斷是否需要在i+1層停止，若是i+1層的花費
大于i層，則我們可以繼續(xù)計算，否則退出。
三 代碼如下：
#include <iostream>
using namespace std ;
const int N = 10 ;
int person[N+1] = 
{0 , 2 , 5 , 7 , 3 , 5 , 2 , 6, 2 , 6 , 3} ;
int floor2()
{
//先計算出在第一層停止的時候 所需要的花費
int T = 0;
int N1 = 0 ; //在第一層以下下的人數(shù)
int N2 = person[1] ; //在第一層處下的人數(shù)
int N3 = 0 ; //在第一層之上下電梯的人數(shù)
int floor = 1 ;
for(int i = 2 ; i <= N ;i++) //先計算出第1層停止需要爬取的樓層數(shù)目
{
T += person[i] * (i - 1) ;
N3 += person[i] ;
}
for(int i = 2 ; i <= N ;i++)
{
if(N1 + N2 <= N3) //說明第i+1層的結(jié)果會大于第i層
{
T += N1 + N2 - N3 ;
N1 += N2 ;
N2 = person[i] ;
N3 -= person[i] ;
floor = i ;
}
else //否則第i層的結(jié)果已經(jīng)最小，故不需要計算第i+1層
break ;
}
return floor ;
}
int floor1() //使用簡單算法計算
{
int tempfloor = 0 ;
int min = 6553 ;//存儲最小值
int floor = 1 ;//存儲停靠的樓層
int i , j ;
for( i = 1 ; i <= N ;i++) //表示第i樓層電梯停靠
{
tempfloor = 0 ;
for( j = 1 ; j < i ;j++)
tempfloor += (i - j) * person[j] ;
for(j = i + 1 ; j <= N ; j++)
tempfloor += (j - i) * person[j] ;
if(min > tempfloor)
{
min = tempfloor ;
floor = i ;
}
// cout<<"tempfloor"<<i<<":"<<tempfloor<<endl;
}
return floor ;
}
int main()
{
int temp1 = floor1() ;
int temp2 = floor2() ;
cout<<temp1<<" "<<temp2<<endl ;
getchar() ;
return 0 ;
}