[编程之美] PSet1.8 小飞的电梯调度算法

2024年5月3日 互联网

亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间，每层都有人上下，电梯每层都停。实习生小飞常常会被每层都停的电梯弄的很不耐烦，于是他提出了这样一个办法：


由于楼层并不算太高，那么在繁忙的上下班时间，每次电梯从一层往上走时，我们只允许电梯停在其中的某一层。所有乘客从一楼上电梯，到达某层后，电梯停下来，所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候，每个乘客选择自己的目的层，电梯则计算出应停的楼层。

问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？

解法一：暴力枚举法。从第1层枚举到第N层，求出电梯在x层停的话，所有乘客需要怕多少层楼。求出最少的那层即可。O(N^2)

int findTargetFloor(int *Peoples ， int N)
{int nFloors=0;int minFloors = -1;int targetFloor = 0;for(int i=1 ; i<=N ; i++){for(int j=1 ; j<i ; j++)nFloors+=Peoples[j]*(i-j);for(int j=i+1 ; j<=N ; j++)nFloors+=Peoples[j]*(j-i);if(nFloors < minFloors || minFloors == -1){minFloors = nFloors;targetFloor = j;}}return targetFloor;
}


解法二：书上提供的O(N)的动态规划的算法。

假设电梯停在i层楼，可以计算出所有乘客要爬楼层的层数为Y,假设此时有N1个乘客在i层楼以下，N2个乘客在I层楼，N3个乘客在I层楼以上，则当电梯停在i+1层的时候，N1+N2个乘客要多下一层楼，共多下N1+N2层，N3个乘客要少往上面爬一层楼，少上N3层楼，此时Y(i+1) = Y(i) + N1+N2-N3，很显然，当N1+N2<N3的时候，Y不断减小。Y1很容易算出来，另外我们还可以看出，N1+N2是递增的，N3是递减的，所以N1+N2一旦大于N3的时候，我们直接退出循环即可，没有必要再计算下去了。

int findKFloor(int *Peoples , int N)
{int targetFloor = -1;int minFloors = 0;int N1=0 ;int N2=Peoples[1];int N3=0 ;for(int i=2 ; i<=N ; i++){N3 +=Peoples[i];minFloors += Peoples[i]*(i-1);}for(int i=2; i<=N ; i++){if(N1+N2<N3){minFloors += N1+N2-N3;targetFloor = i;N1 = N1+N2;N2 = Peoples[i];N3 = N3-Peoples[i];}elsebreak;}return targetFloor;
}

扩展问题：
如果往上爬楼梯比较累，往下走较容易，假设往上走一层耗费k单位的能量，往下走一层只耗费1单位的能量。题目条件改为让所有人消耗的能量最少，这个问题怎么解决呢？ 

//向上爬一层需要UPCOST能量
//向下爬一层需要1单位能量
//总共有N层楼（下标从1开始）
int findKFloor(int *Peoples , int N)
{int targetFloor = -1;int N1 = 0;int N2 = Peoples[1];int N3 = 0;int minFloors = 0;//最低能量for(int i=2 ; i<=N ; i++){N3 += Peoples[i];//在第一层以上的人数之和minFloors += Peoples[i]*(i-1)*UPCOST;//最低能量代价}for(int i=2 ; i<=N ; i++){if(N1+N2 < N3*UPCOST){targetFloor = i;minFloors += N1+N2-N3*UPCOST;N1 = N1+N2;N2 = Peoples[i];N3 = N3-Peoples[i];}else break;}return targetFloor;
}

最新文章