趣味算法题-电梯调度问题
六安毛坦厂中学-上海财经大学本科招生网
趣味算法题-电梯调度问题
这是《编程之美》中的一道题，刚开始
题目比较简单，
但是逐步推进之后的问题也有些难度，这样由简单到难的一
步步深入的思想比较
值得学习。
最初的问题
假如电梯在高峰期间只允许在某一层停留，所有的乘客在一
楼上电梯，到达某层后，所有乘客从电梯下来，到达自己要
去的楼层，在一楼的时候所有乘客选出自己要
去的楼层，电
梯根据所有乘客选择的楼层信息得出要停留的楼层。
那么，电梯停留在那一层，能够保证这次乘坐电梯的所有乘
客爬楼梯的层数之和最少。
问题的分析和解法
该问题本质上是一个优化问题，首先为则个问题找到一个合
适的抽
象模型。从问题中可以看出，有两个因素会影响到最
后的结构：乘客的数目即需要停留的楼层，因此，我
们可以
从统计到达各层的乘客数目开始分析。
假设楼层总共有N层，电梯停留在
X层，要去第i层的乘客
总数目是Tot[i]，这样，所爬楼梯的总数就可以表示出老。
因此，我们就是要找到一个整数X使得这个总数的值最小。
解法
首
先思考简单解法，可以从第1层开始枚举X一直到第N
层，然后再计算出如果电梯在第X层的话，所有乘
客总共需
要爬多少层楼。这是最为直接的一个解法。可以看出，这个
算法需要两重循环来完成计
算
int n=0;这个表示电梯所在的最高楼层
int
nPerson[] = new int[n+1];这个数组表示要去每
一层的乘客数
上面的两个变量应该是给出的，这里只是示意代
码没有初始化。
int n
Floor,nMinFloor,nTargetFloor;分别表示电梯停
在第n层时候的结果，
目前为止的最小结果，最小结果所停
的楼层。
nTargetFloor
= -1;考虑到初始化最小结果和最小结
果所砸的楼层，所以先设定为一个非法值
循环遍历每个楼层的结果，算出本层的结果，如
果比之前结果小，就替换之前结果
for(int i = 1; i <= n; i++){
nFloor = 0;
计算本层以下的楼层的人的总消耗
for(int j =1; j < i; j++){
nFloor += nPerson[j]*(i-j);
}
计算本层以上的楼层的人的总消耗
for(int j = i+1; j
nFloor){
nMinFloor = nFloor;
nTargetFloor = i
}
}2
这个基本解法的时间复杂度为O（N2）
解法的优化
我们希望尽可能地减少算法的时间复杂度。那么，是否有可
能在低于O（N2）
的规则下求出这个问题的解呢？
我们可以有如下的思路：
假设电梯停在第i层，显然我们可以计算出所有乘客总共要
爬楼梯的层数Y。如果有N1个乘客目的楼
层在第i层楼一
下，有N2个乘客在第i层楼，还有N3个乘客在第i层以上。
这个时候，如果
电梯改停在第i-1层，所有目的地在第i-1层
一下的蹭课可以少爬一层，总共可以少爬N1层，所有
目的
地在i层及以上的乘客都需要多爬1层，总共需要多爬N2+N3
层。因此
，乘客总共需要爬的层数为Y-N1+（N2+N3）=Y-
（N1-N2-N3）层。
反之，如果电梯在i+1层停那么乘客总共需要爬的层数为Y+
（N1+N2-N3）层。由此
可见，当N1>N2+N3时，电梯在第
i-1层停更好，乘客走的楼层数减少N1-N2-N3层；当
N1+N2
int n=0;这个表示电梯所在的最高楼层
int
nPerson[] = new int[n+1];这个数组表示要去每
一层的乘客数
上面的两个变量应该是给出的，这里只是示意代
码没有初始化。
int
nMinFloor = 0,nTargetFloor =
1;分别表示目前
为止的最小结果，最小结果所停的楼层。
int N1
= 0 , N2 = nPerson[1] , N3 =
0;分析中所说的
N1,N2,N3创建和初始化
求出第二层时候的N3值并初始化
for(int k = 2; k <=
n;k++){
N3 += nPerson[k];
nMinFloor += nPerson[k] *(k-1);
}
从第二层开始按照上述方法求出最优值
for(int i =
2; i <= n i++){
if( (N1 + N2) <
N3){如果i+1层更好，就替换
最小结果，
nTargetFloor = i
nMinFloor
+= (N1 +N2 - N3);
N1 += N2;
N2 = nPerson[i];
N3 -= nPerson[i];
}else{如果上面的楼层不会更好，就不用再查
看了。
break;
}
}2
问题扩展 <
br>往上爬楼梯，总比往下走是要累的，假设往上爬一个楼层，
需要消耗k个单位的能力，而往下走需
要消耗一个单位的能
量，那么如果题目条件改为让所有人消耗的能量最少，这个
问题怎么解决呢
？
分析
其实这个问题并没有变难太多，只是在前面的思考的前提下
放入一个新的考
虑：上下楼消耗能量。这个需要在计算的时
候上楼就要乘以一个参数K(因为能量是下楼的k倍嘛),其
他
的考虑都还一样。
int n=0,k =
1;这个表示电梯所在的最高楼层和上楼梯需要
消耗的能量
int
nPerson[] = new int[n+1];这个数组表示要去每
一层的乘客数
上面的变量应该是给出的，这里只是示意代码没
有初始化。
int
nMinFloor = 0,nTargetFloor =
1;分别表示目前
为止的最小结果，最小结果所停的楼层。
int N1
= 0 , N2 = nPerson[1] , N3 =
0;分析中所说的
N1,N2,N3创建和初始化
求出第二层时候的N3值并初始化
for(int m = 2; m <=
n;m++){
N3 += nPerson[m];
nMinFloor += nPerson[m] *(m-1);
}
从第二层开始按照上述方法求出最优值
for(int i = 2; i <=
n i++){
if( k*(N1 + N2) <
N3){如果i+1层更好，就替
换最小结果，
nTargetFloor = i
nMinFloor
+= (k*(N1 +N2) - N3);
}
N1 += N2;
N2 =
nPerson[i];
N3 -= nPerson[i];
}17181920
补充说明
其实目前为止的逻辑过于不切实际，因为实际中在高层电梯<
br>中不会出现只停一层的情况，而且如果有类似的政策的话，
比较低的楼层的人会直接选择爬楼去而
不去按电梯（即使是
统计好人数也会在计算总体的消耗上有很大的不同）。