编程之美-小飞的电梯调度算法
public class AptElevator {/** * 编程之美 小飞 电梯调度算法 * 在繁忙的时间，每次电梯从一层往上走时，我们只允许电梯停在其中的某一层。 * 所有乘客都从一楼上电梯，到达某层楼后，电梯听下来，所有乘客再从这里爬楼梯到自己的目的层。 * 在一楼时，每个乘客选择自己的目的层，电梯则自动计算出应停的楼层。 * 问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？ 思路:当电梯停靠在第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的值,依次调整以得到最优解. */private int targetFloor;//电梯应该停靠在哪一层private int minStairs;//不能直达的乘客共要走多少层楼梯public static void main(String[] args) {AptElevator elevator=new AptElevator();int[] person={0,2,5,7,8,9,6,6,1,4,4,8,5,2,4,5,8,6,3,3,5,9,9,6,6,9,8,8,5,5,9,6,6,3};//person[i]表示要到第i层的人数elevator.opt(person);System.out.println(elevator.targetFloor+","+elevator.minStairs);}public AptElevator(){this.targetFloor=0;this.minStairs=0;}public void opt(int[] person){if(person==null){return;}if(person.length<2){//如果没有人到二楼或者更高，那就不用坐电梯了return;}int N=person.length-1;targetFloor=2;//先让电梯停在二楼，计算N1,N2int N1=0;int N2=person[2];int N3=0;//电梯停在二楼，计算N3以及总楼梯数MinFloorfor(int j=3;j<=N;j++){N3+=person[j];minStairs+=person[j]*(j-targetFloor);}//让电梯依次改停在3楼、4楼...N楼,出现更优解时,则调整电梯停靠层数以及N1,N2,N3for(int i=3;i<=N;i++){if(N1+N2<N3){targetFloor=i;N1=N1+N2;N2=person[i];N3=N3-person[i];minStairs+=N1+N2-N3;}}}}