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