当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

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

发表于: 2012-06-20   作者:bylijinnan   来源:转载   浏览:
摘要: public class AptElevator { /** * 编程之美 小飞 电梯调度算法 * 在繁忙的时间,每次电梯从一层往上走时,我们只允许电梯停在其中的某一层。 * 所有乘客都从一楼上电梯,到达某层楼后,电梯听下来,所有乘客再从这里爬楼梯到自己的目的层。 * 在一楼时,每个乘客选择自己的目的层,电梯则自动计算出应停的楼层。 * 问:电梯停在哪

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,N2
		int N1=0;
		int N2=person[2];
		int N3=0;
		//电梯停在二楼,计算N3以及总楼梯数MinFloor
		for(int j=3;j<=N;j++){
			N3+=person[j];
			minStairs+=person[j]*(j-targetFloor);
		}
		//让电梯依次改停在3楼、4楼...N楼,出现更优解时,则调整电梯停靠层数以及N1,N2,N3
		for(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;
			}
		}
	}
	
}

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
分析: 1)直接想法是穷举法,依次算出电梯停靠在第一层到第N层乘客所要爬的总层数,找出最小值。
题目:   亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间,每层都有人上下,电梯每层
编程任务:电梯调度 结对人员:左少辉-12061209,杨昊兰-12061202,吕雨朗 一、此次软工作业确实是
小飞的电梯调度算法 1. 问题描述: 亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间,每
结对成员: 杨鹏飞(193) 邓嘉(164) 老师给定的电梯调度程序是一个C#命令行程序,其中电梯调度算
首先来看一个实时排名算法 参考文献 某海量用户网站,用户拥有积分,积分可能会在使用过程中随时更
关于结对编程   结对编程的队友:梁鸿(195)   我觉得结对编程与自己一个人编程有很大的区别。
3、题目:能否快速找出一个数组(简单起见,数组中元素值各不一样)中的两个数字,让这两个数字之和
今天开始看编程之美 。第一个问题是CPU的使用率控制,微软的问题果然高大上,我一看就傻了,啥也不
输入:乘客请求事件,所有电梯状态 输出:电梯命令 其中, 电梯状态 电梯命令 乘客请求事件 最高层
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号