编程之美-电梯问题-java版
?原文来自:http://www.dev26.com?<!--EndFra-->
在办公楼的电梯里高层期间，每层都有人上下。电梯呢只要每层有一个人都有停一次。这样比较麻烦，对于比较低的楼层（6层）,每次电梯从一层往上走时，我们只允许电梯停在其中的某一层，然后所有的乘客爬楼梯到自己的目的层。在一楼时，每一位乘客选择自己的楼层，电梯根据每层的人数来计算出应该停的楼层.
问:电梯停在哪一层，能够保证这次乘坐电梯的所以乘客爬楼梯层数之和最少.
分析与解法:
???该问题本质是一个优化问题。首先为这个问题找一个合适的抽象模型。从问题中可以看出，有两个因素会影响到最后的结果：乘客的数目及需要停的目的楼层。因此我们可以统计到达各层的乘客数目开始分析。
假设楼层总共有N层，电梯停在第X层，要去第i层的乘客数目总数为Tot[i],这样，所以爬楼梯的总数就是∑Ni=1??{Tot[i]*|i-x|}的值最少.
解法一:
???首选考虑简单解法.
???可以从第1层开始枚举x一直到N层，然后在计算出如果电梯在x层停的话，所以乘客总共有爬多少层。这是最直接的一种方法。
这个需要一个双重循环来完成计算:时间复杂度为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)
?
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-->