编程之美-电梯调度算法
一问题描述：
所有的员工均在1楼进电梯的时候，选择所要到达的楼层。
然后计算出停靠的楼层i，当到达楼层i的时候，电梯停止。
所有人走出电梯，步行到所在的楼层中。
求所有人爬的楼层数目和的最小值。
二 问题解决方法：
二 解决方案：
(1)使用简单的方法，直接将楼层从1到n开始遍历
sum(person[i] * |i - j| ) 此表达式为一个双重循环，i与j均为1-n的循环。
j下标表示电梯停靠的楼层。
person数组表示，对应i层的下电梯的人数。此算法负责度为o(n*n)
对应的j是上述和为最小的一层即为所求。 上面的算法复杂度为o(n)
(2)下面考虑一个简单的算法，使其复杂度达到o(n)
考虑假如电梯停靠在某一楼层i处，假设在i处下楼的客人为N2,
在i以上楼层的客人数目为N3 ，在i一下楼层的客人数目为N1。
且将电梯在i层停止时，全部人员的路程之和记为T。
那么加入电梯在i-1层停的话，则原来i层之上的人需要多爬一层，即增加了N3
第i层的人需要多爬一层，则结果增加了N2, i层之下的人则少爬了一层，结果减去N1
所以第i-1层的结果为 T - N1 + N2 + N3 。即结果可以即为 T -(N1 - N2 - N3)
下面考虑在i+1层的结果，若电梯在i+1层停止的话，原来i层之上的客户都会少爬一层，
则结果减少N3 ，而i层之下的人员则都会多爬一层即增加了N1 ，第i层的人员都会多爬一层
即为增加了N2 。则结果为 T + N1 + N2 - N3
综上我们得出，
(1)若N1 > N2 + N3的时候， 我们在第i-1层 选择电梯停止最好。
(2)若N1 + N2 < N3的时候， 我们选择在第i+1层停止电梯最好。
下面我们可以先计算出来当i=1时候的T ，然后判断是否需要在i+1层停止，若是i+1层的花费
大于i层，则我们可以继续计算，否则退出。
三 代码如下：
#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 ; //在第一层以下下的人数
int N2 = person[1] ; //在第一层处下的人数
int N3 = 0 ; //在第一层之上下电梯的人数
int floor = 1 ;
for(int i = 2 ; i <= N ;i++) //先计算出第1层停止需要爬取的楼层数目
{
T += person[i] * (i - 1) ;
N3 += person[i] ;
}
for(int i = 2 ; i <= N ;i++)
{
if(N1 + N2 <= N3) //说明第i+1层的结果会大于第i层
{
T += N1 + N2 - N3 ;
N1 += N2 ;
N2 = person[i] ;
N3 -= person[i] ;
floor = i ;
}
else //否则第i层的结果已经最小，故不需要计算第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 ;
}