电梯算法
战略发展部-安全标签
2023年2月23日发(作者：梅雨潭)java电梯算法_编程之美之⼩飞的电梯调度算法（多种解法）--
-Java语⾔
1.题⽬情景
我们假设都是从⼀楼上电梯的，⽽⾄于讯电梯停在其中的某⼀层。即所有的乘客都从⼀楼上电梯，到达某层之后，电梯停下来，所有乘客再
从这⾥爬楼梯到⾃⼰的⽬的层。在⼀楼的时候，每个乘客选择⾃⼰的⽬的层，电梯则⾃动计算出应停的楼层，并且能够保证该层停使得所有
乘客爬楼梯的层数之和最少。
输⼊：第⼀⾏楼层数N，乘客⼈数n；第⼆⾏有n个数，表⽰乘客选择的⽬的层。
输出：输出为停⽌楼层和总共需要爬的楼梯。
2.解法⼀
第⼀种⽅法就是采取暴⼒求解的办法，采⽤双重循环的⽅式，外循环控制停的楼层，内循环计算当前楼层停，总共需要爬多少楼层，并保留
最⼩值及其相应停电梯的楼层。
具体代码如下：
1_8;
.*;
publicclassElevatorController{
publicstaticvoidmain(String[]args){
//TODOAuto-generatedmethodstub
Scannersc=newScanner();
intN=t();
intn=t();
intpassenger[]=newint[n];
for(inti=0;i
{
passenger[i]=t();
}
intstopFloor=0;
intminFloor=_VALUE;
for(inti=1;i<=N;i++)//控制停电梯的楼层
{
inttemp=0;
for(intj=0;j
{
temp+=(passenger[j]-i);
}
if(temp
{
minFloor=temp;
stopFloor=i;
}
}
n("最佳停电梯的楼层为："+stopFloor);
n("乘客需要爬楼梯的总数为："+minFloor);
();
}
}
运⾏结果如下：
106
4839105
最佳停电梯的楼层为：5
乘客需要爬楼梯的总数为：15
这种⽅法⽐较简单直接，因此复杂度较⾼，为O(N*n)，所以接下来我们想办法降低复杂度。如果n⼤于N，那么可以将上述程序做⼀些修改
也可以稍微降低复杂度。当n⼤于N时，先计算N层楼每层楼有⼏个乘客，复杂度为O(n)，然后再遍历，遍历过程复杂度为O(N*N)，因此下
⾯程序总复杂度为O(n+N*N)。
1_8;
.*;
publicclassElevatorController{
publicstaticvoidmain(String[]args){
//TODOAuto-generatedmethodstub
Scannersc=newScanner();
intN=t();
intn=t();
intpassenger[]=newint[N+1];
for(inti=0;i
{
passenger[t()]+=1;
}
intstopFloor=0;
intmaxFloor=_VALUE;
for(inti=1;i<=N;i++)//控制停电梯的楼层
{
inttemp=0;
for(intj=1;j<=N;j++)//计算停在当前楼层，总共需要爬的楼层
{
temp+=(j-i)*passenger[j];
}
if(temp
{
maxFloor=temp;
stopFloor=i;
}
}
n("最佳停电梯的楼层为："+stopFloor);
n("乘客需要爬楼梯的总数为："+maxFloor);
();
}
}
3.解法⼆
我们假设停在第i层楼，那么当前楼层需要爬的总楼层是Y。如果有N1个乘客在楼层i以下，有N2个乘客在第i层楼，还有N3个乘客在第i层以
上。那么如果现在电梯停在i-1层，则总共需要爬Y-N1+(N2+N3)层，如果改在i+1层，那么总共需要爬Y-N3+(N2+N1)层，所以我们可以
换个思路，当电梯从⼀楼逐渐往上⾛的时候，当N2+N1-N3=0，则可以停下来，因为往上爬的过
程中N3是逐渐减⼩的，⼀旦N2+N1-N3>=0之后，那么随着楼层往上爬，这个差值会越来越⼤，即代表⼈们要爬的总楼层越来越多，所以
当差值不再为负即可停下来。
实现代码如下：
1_8;
r;
publicclassElevatorController2{
publicstaticvoidmain(String[]args){
//TODOAuto-generatedmethodstub
Scannersc=newScanner();
intN=t();
intn=t();
intFloor[]=newint[N+1];//⽤来统计每个楼层停下的⼈数
for(inti=0;i
Floor[t()]+=1;
();
intstopFloor=1;//先从第⼀层开始推算
intN1=0;//停在第⼀层的话，第⼀层是最低的，那么N1则为0
intN2=Floor[1];//假设第⼀次停在第⼀层，求出⽬标楼层是当前楼层的⼈数.
//计算N3的初始值和停在1层对应的nMinFloor值
intN3=0;
intnMinFloor=0;
for(inti=2;i<=N;i++)
{
N3+=Floor[i];
nMinFloor+=Floor[i]*(i-1);
}
//然后逐渐往上⾛，寻找最优⽬标楼层。
for(inti=2;i<=N;i++)
{
if(N1+N2-N3<0)//即判断往上⾛，爬楼梯总数是否会减少。
{
N1+=N2;
N2=Floor[i];
N3-=Floor[i];
stopFloor=i;//更新停电梯楼层.
nMinFloor+=(N1+N2-N3);//更新爬楼梯总数
}
else
break;
}
n("最佳停电梯的楼层为："+stopFloor);
n("乘客需要爬楼梯的总数为："+nMinFloor);
}
}
以上解法是从第⼀层往上⾛，依次更新相应的数据，直到⽬标值不能再优化时，得到最优值。运⾏结果如下：
106
4839105
最佳停电梯的楼层为：5
乘客需要爬楼梯的总数为：15
4.解法三
其实，还有⼀种解法，有n个乘客都有⾃⼰需要去的楼层，在停⽌楼层下电梯之后，⼤家都要去⾃⼰的⽬标楼层，那么我们假设每位乘客都
已经在⽬的楼层了，那么我们可以将问题转换为，所有乘客在哪⼀层碰头，所需要爬的楼梯最少。⼀般这种会⾯算法，最佳地点应该选择在
中间数，即将每⼀位乘客所在位置，放进⼀个数组并排序取中间数就是最佳会⾯地点。(注：当乘客数为n，则最佳地点就是有序地点集合中
第(n+1)/2个元素代表的地点)。其中这⾥的排序可以⽤桶排序，因为楼层数不会过于庞⼤，那么把每⼀层都当做⼀个桶，然后把相应的⼈
放进去，桶号即数组下标，然后逐个取出就完成了排序，复杂度是线性的。
1_8;
r;
publicclassElevatorController3{
privatestaticint[]calSort(int[]a,intN,intn)
{
int[]res=newint[n];
intk=0;
for(inti=0;i<=N;i++)
{
inttemp=a[i];
while(temp>0)
{
res[k++]=a[i];
}
}
returnres;
}
publicstaticvoidmain(String[]args){
//TODOAuto-generatedmethodstub
Scannersc=newScanner();
intN=t();
intn=t();
intpassenger[]=newint[N+1];
for(inti=0;i
{
passenger[t()]+=1;
}
();
int[]res=calSort(passenger,N,n);//桶排序
intstopFloor=res[(n+1)/2-1];
intnMinFloor=0;
for(inti=1;i<=N;i++)
{
nMinFloor+=(i-stopFloor)*passenger[i];
}
n("最佳停电梯的楼层为："+stopFloor);
n("乘客需要爬楼梯的总数为："+nMinFloor);
}
}
运⾏结果：
108
11278889
最佳停电梯的楼层为：7
乘客需要爬楼梯的总数为：22
---------------------
作者：carson0408
来源：CSDN
版权声明：本⽂为博主原创⽂章，转载请附上博⽂链接！