1.8 小飞的电梯调度算法

题目：有一栋楼，如今设计一种电梯调度算法：电梯在一楼让大家上电梯，然后依据大家选择要到的楼层算出某一楼层i，电梯在i层停下让全部人下电梯，然后大家爬楼梯达到自己的楼层。请问电梯停在哪一层。能够使得这一次的全部乘客爬楼层之和最短？

（一）

最直接最简单的方法就是直接枚举从第一层到最后一层，然后算出电梯停在哪一层会使得全部乘客爬楼层之和最短。

代码例如以下：

int nPerson[]; //nPerson[i]表示到第i层的乘客的数目 int nFloor = 0, nMinFloor = 0; int nTargetFloor = -1; for(int i = 1; i <= N; ++i) { //N代表楼层的总数for(int j = 1; j < i; ++j) nFloor += nPerson[j] * (i - j);for(int j = i + 1; j <= N; ++j) nFloor += nPerson[j] * (j - i);if(nTargetFloor == -1 || nFloor < nMinFloor) {nMinFloor = nFloor;nTargetFloor = i;} }

（二）

思路:当电梯停靠在第i层时,乘客所要爬的总的楼梯数为Y. 如果有N1个乘客要到达的层数<i,有N2个乘客要到达的层数==i,有N3个乘客要到达的层数>i. 所以有: (1)当电梯改停在i-1,则 Y+(N2+N3-N1) (2)当电梯改停在i+1,则 Y+(N1+N2-N3) 所以当后面那部分的值<0时(如(2)的N1+N2<N3),则加上负数后总的楼梯数比原来的小,即更优解. 因此,我们能够从第一层開始,用以上策略,考察N1,N2,N3的值,依次调整以得到最优解.

int nPerson[]; //nPerson[i]表示到第i层的乘客的数目 int nFloor = 0, nMinFloor = 0; int nTargetFloor = 1; int N1 = 0, N2 = 0, N3 = 0; for(N1 = 0, N2 = nPerson[1], N3 = 0, i = 2; i <= n; ++i) { //n代表楼层的数目N3 += nPerson[i];nMinFloor += nPerson[i] * (i - 1); } for(int i = 2; i <= n; ++i) {if(N1 + N2 < N3) {nTargetFloor = i;nMinFloor += (N1 + N2 - N3);N1 += N2;N2 = nPerson[i];N3 -= nPerson[i];}else break; }

转载于:https://www.cnblogs.com/gccbuaa/p/6872531.html

总结

以上是生活随笔为你收集整理的1.8 小飞的电梯调度算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。