《编程之美》小飞的电梯调度算法

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

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

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

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

解法二：动态规划。假设电梯停在第x层，已知目的楼层在x层的有N2人，在x层以下的有N1人，在x层以上的有N3人。此时总花费为sum。则往上走一层的话，总花费变为sum + N2 + N1 - N3。那么初始状态电梯停在第一层，向上进行状态的变迁，开始时N2 + N1 - N3 < 0。sum越来越小，直到某一层N2 + N1 >= N3，就没有必要在往上走了。这时已求出最合适的楼层了。

解法三：我的方法。哈哈。其实没有那么复杂。假设只有两个人，一个去9层，一个去2层，那么不管电梯停在2至9层中间的任何楼层，两个人的总花费都是7.就比如在数轴上点2和点9中间的任何点距离2和9的距离之后都是7。那么停在哪都无所谓了。接着我们扩展开来，假设有N个人，他们的目标楼层分别是2,3,3,4,5,5,5,7,7,8,9。按我们的想法，对于两端的（2,9）电梯只要停在他们之间都一样。同理对于（3,8）电梯只要停在他们中间都一样……。最终电梯只要停在中间那个数即可。也就是中位数。原来弄半天只需求出中位数即可啊。如果N是偶数个的话，停在中间那两个数任何一个都可以的。欢迎大家对我的解法拍砖。代码就不用了吧。

扩展问题的解法：

如果往上爬楼梯比较累，往下走较容易，假设往上走一层耗费k单位的能量，往下走一层只耗费1单位的能量。此时就不适合用我的解法三了，解法二更加适合。代码如下：

int controlElevator(int nPerson[], int nfloor, int upWeight){
    int targetFloor = ;
    int minFloor = ;
    int N1 = ;
    int N2 = nPerson[];
    int N3 = ;
    int i = ;
    for(i = ; i <= nfloor; i++){ //i表示大众意义上的第i层
        N3 += nPerson[i];
        minFloor += (nPerson[i] * (i - ) * upWeight);
    }
    for(i = ; i <= nfloor; i++){
        if(N1 + N2 < N3 * upWeight){
            minFloor += (N1 + N2 - N3 * upWeight);
            N3 -= nPerson[i];
            N1 += N2;
            N2 = nPerson[i];
            targetFloor = i;
        }
        else
            break;
    }
    return minFloor;
//  return targetFloor;
}
           

下面附上我的解法三的代码：

int main(){ 
    int nPerson[]={,,,,,,,,};
    int left=, right=;
    while(right-left > ){
        while(nPerson[left] == )
            ++left;
        nPerson[left]--;
        while(nPerson[right] == ){
            if(right < left)
                break;
            --right;
        }           
        nPerson[right]--;
    }
    cout<<left+<<endl; 
    return ;
}