1.8 小飞的电梯调度算法

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

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

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

分析与解法

该问题本质上是一个优化问题。首先为这个问题找到一个合适的抽象模型。从问题中可以看出，有两个因素会影响到最后的结果：乘客的数目及需要停的目的楼层。因此，我们可以从统计到达各层的乘客数目开始分析。

假设楼层总共有N层，电梯停在第x层，要去第i层的乘客数目总数为Tot[i]，这样，所爬楼梯的总数就是。

因此，我们就是要找到一个整数x，使得的值最小。

解法一

首先考虑简单解法。

可以从第1层开始枚举x一直到第N层，然后再计算出如果电梯在第x层楼停的话，所有乘客总共要爬多少层楼。这是最为直接的一个解法。

可以看出，这个算法需要两重循环来完成计算（伪代码如清单1-1所示）。

代码清单1-11

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

这个基本解法的时间复杂度为O（N2）。

解法二

我们希望尽可能地减少算法的时间复杂度。那么，是否有可能在低于O（N2）的规模下求出这个问题的解呢？

我们可以进一步地分析。

假设电梯停在第i层楼，显然我们可以计算出所有乘客总共要爬楼梯的层数Y。如果有N1个乘客目的楼层在第i层楼以下，有N2个乘客在第i层楼，还有N3个乘客在第i层楼以上。这个时候，如果电梯改停在i-1层，所有目的地在第i层及以上的乘客都需要多爬1层，总共需要多爬N2+N3层，而所有目的地在第i-1层及以下的乘客可以少爬1层，总共可以少爬N1层。因此，乘客总共需要爬的层数为Y-N1+（N2+N3）=Y-（N1-N2-N3）层。

反之，如果电梯在i+1层停，那么乘客总共需要爬的层数为Y+（N1+N2-N3）层。由此可见，当N1>N2+N3时，电梯在第i-1层楼停更好，乘客走的楼层数减少（N1-N2-N3）；而当N1+N2<N3时，电梯在i+1层停更好；其他情况下，电梯停在第i层最好。

根据这个规律，我们从第一层开始考察，计算各位乘客需要爬楼梯的数目。然后再根据上面的策略进行调整，直到找到最佳楼层。总的时间复杂度将降为O（N），代码如清单1-12所示。

代码清单1-12

    int nPerson[];       // nPerson[i]表示到第i层的乘客数目
    int nMinFloor, nTargetFloor;
    int N1, N2, N3;
    nTargetFloor=1;
    nMinFloor=0;
    for(N1=0, N2=nPerson[1], N3=0, i=2; i <=N; i++)
    {
        N3+=nPerson[i];
        nMinFloor+=nPerson[i] * (i -1);
    }
    for(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;
    }
    return(nTargetFloor, nMinFloor);

扩展问题

1．往上爬楼梯，总是比往下走要累的。假设往上爬一个楼层，要耗费k单位的能量，而往下走只需要耗费1单位的能量，那么如果题目条件改为让所有人消耗的能量最少，这个问题怎么解决呢？

这个问题可以用类似上面的分析方法来解答，因此笔者不再赘述，留给读者自行解决。

2．在一个高楼里面，电梯只在某一个楼层停，这个政策还是不太人性化。如果电梯会在k个楼层停呢？读者可以发挥自己的想象力，看看如何寻找最优方案。