编程之美-电梯问题-java版

 原文来自:http://www.dev26.com  <!--EndFra-->

在办公楼的电梯里高层期间，每层都有人上下。电梯呢只要每层有一个人都有停一次。这样比较麻烦，对于比较低的楼层（6层）,每次电梯从一层往上走时，我们只允许电梯停在其中的某一层，然后所有的乘客爬楼梯到自己的目的层。在一楼时，每一位乘客选择自己的楼层，电梯根据每层的人数来计算出应该停的楼层.

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

分析与解法:

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

假设楼层总共有N层，电梯停在第X层，要去第i层的乘客数目总数为Tot[i],这样，所以爬楼梯的总数就是∑^N_i=1  {Tot[i]*|i-x|}的值最少.

解法一:

   首选考虑简单解法.

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

这个需要一个双重循环来完成计算:时间复杂度为O(N²)

解法二:

  进一步分析，假设电梯停在第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)

 

package com.floor;
     
/***
 * 电梯优 化方法
 *
 * */
public class Floor {
    public static void main(String[] args) {
        getMinFloors(4, 1);
        betterFloors();
    }
     
    // 双层循环法,计算所以乘客要爬多少层楼梯。。时间复杂度为o(N^2)
    public static void getMinFloors(int nTargetFloor, int nMinFloor) {
        // 以下是要去往电梯各层的人数
        int[] persons = { 0, 2, 0, 1, 3, 5, 8, 4, 6, 0 };
        int N = 9;// 电梯一共有多少层
        for (int i = 1; i <= N; i++) {
            int nFloor = 0;
            for (int j = 1; j < i; j++) {
                nFloor += persons[j] * (i - j);// 计算往下爬的楼层数
            }
            for (int j = i + 1; j <= N; j++) {
                nFloor += persons[j] * (j - i);// 计算往上爬的楼层数
            }
            if (nTargetFloor == -1 || nMinFloor > nFloor) {
                nMinFloor = nFloor;
                nTargetFloor = i;
            }
            System.out.println("如果停在第" + i + "层需要爬" + nFloor + ":趟电梯");
        }
    }
     
    // 更优方法
    public static void betterFloors() {
        // 以下是要去往电梯各层的人数
        int[] persons = { 0, 2, 0, 1, 3, 5, 8, 4, 6, 0 };
        int N = 9;// 电梯一共有多少层
        int nTargetFloor = 1;
        int nMinFloor = 0;
        int N1 = 0, N2 = persons[1], N3 = 0;
        for (int i = 2; i <= N; i++) {
            N3 += persons[i];
            nMinFloor += persons[i] * (i - 1);//先计算出所以应该要爬的楼层总和
        }
        for (int i = 2; i <= N; i++) {
            if (N1 + N2 < N3) {
                nTargetFloor = i;
                nMinFloor += (N1 + N2 - N3);
                N1 += N2;
                N2 = persons[i];
                N3 -= persons[i];
            } else {
                break;
            }
        }
        System.out.println("优化方法结果:停在第" + nTargetFloor + "层要爬:" + nMinFloor
                + "次");
    }
     
}

<!--EndFragment-->