电梯调度编程

题目

一栋10层的大楼（楼层编号1-10），设有一台无限载重的电梯，初始时电梯停在1层。电梯移动1层的耗时为1，在某一层停靠的耗时为1（时间初始为0）。为了使得乘客等待的时间（电梯在目的层的停靠时刻 - 乘客发出请求时刻）总和最小，请你编写一个程序来进行电梯调度。

输入有5个请求，每个请求一行，格式为请求时刻 起始楼层数 去往方向，其中方向为0代表向上去往10层，为1代表向下去往1层。
输出每次对应的决策，每一行的输出格式为xx时，停靠在x楼。其中，“xx时刻”指的是在某层楼停靠的时刻，且不算入在该层的停靠时间。如：

1.当0时刻时，电梯此时在1层，输入有0 1 0，那么电梯从1层接客（1s）前往10层（9s），应输出10时，停靠在10楼（1+9=10）。此时，该乘客等待时间为(10-0=)10。
2.当0时刻，电梯此时在1层，输入有0 2 0，那么电梯从1层前往2层（1s），接上乘客（1s），前往10层（8s），应输出10时，停靠在10楼（1+1+8=10）。此时，该乘客等待时间为(10-0=)10s。
最后输出完成5个请求（所有乘客都到达目的地）后，各乘客的等待时间总和。

要求

请自己设计5组测试用例，且具有一定代表性，用以验证程序是否是最小耗时。

编程语言选择C或C++都可以，但需要符合编码规范，且必须要有注释。要求在github上建立一个仓库，将本次作业代码提交到该仓库，并在博客开头给出仓库地址。注意：commit信息要遵守一定的git规范（可参看：git commit 规范指南），git必须使用命令行操作，不要使用github图形界面（可参看：廖雪峰Git教程）。

写一篇博客，在博客中描述在编码过程中，程序的不断优化过程。并列出一张表格，记录编写程序的代码行数、调试的bug数 、完成该次作业总耗时。

思路

引入时间变量time记录总时间,运行到每个点判断向上和向下的请求数并执行较大者（向下的请求数=目标为1楼的请求个数+此时电梯下方未上电梯的请求个数，向上的请求数同理。当某一请求的请求时刻>time或已经登上电梯时，该请求不纳入计算。），每次运行到请求点或目的地时再执行判断，直到所有乘客都到达目的地。

实现方式

把5个请求（a,b,c）输入到结构体变量数组request[5]中，并按起始楼层从低到高将数组排序。

代码1.0(不完满）

#include<stdio.h>
int main()
{
	
	struct request
		{	
			int a;	int b;	int c;	
		}
	 request[5],temp;//定义结构体数组request和变量temp，用于于存入请求和暂存排序交换。 
	int i,j,down=0,up=0,time=0,sum_c=0,t[20],f[20],un_down=0,un_up=0,down_ac,up_ac,down_to_1=0,up_to_10=0,above=0,below=0,ac=0,f_now;
	//a[20]用来存目标楼层 
	for(i=0;i<5;i++)
		scanf("%d%d%d",&request[i].a,&request[i].b,&request[i].c);//输入5个请求赋值到结构体变量数组中 。 
	for(i=1;i<5;i++)
		{
			sum_c+=request[i].c;
			if(request[i].b<request[i-1].b)
				{
					temp=request[i];request[i]=request[i-1];request[i-1]=temp;
				}//按起始楼层从低到高排序数组。 
		}
	for(time=0; ;time++)
	{	for(i=0;i<5;i++)
		{
			if(request[i].b!=0)
			{
				if(request[i].b<f_now)
					below++;//below记录此时电梯下方且未上电梯的请求个数
				else
					above++;//above记录此时电梯上方且未上电梯的请求个数
			}
		}
		down=sum_c+below;//向下的请求数=目标为1楼的请求个数+此时电梯下方且未上电梯的请求个数
		up=5-sum_c+5-below;//向下的请求数=目标为10楼的请求个数+此时电梯上方且未上电梯的请求个数
		for(ac=1;;)
		{
			if(down>=up)
			{
				if(i==0)
				f_now=1;
				else
				f_now=request[i-1].b;
				if(f_now==1)
					for(i=0;i<5;i++)
					if(request[i].c==1)
					{
						request[i].b=0;down_to_1=1;//down_to_1=1表示向下到一楼的乘客已经到达 
					}
				
			}
			else 
			{
				if(i=4)
				f_now=10;
				else
				f_now=request[i+1].b;
				if(f_now==10)
					for(i=0;i<5;i++)
					if(request[i].c==10)
					{
						request[i].b=0;up_to_10=1;
					}
			}
			for(j=0;j<5;j++)
				if(request[j].b==f_now)
				{
					t[ac]=time;f[ac]==f_now;ac++;//ac记录电梯第几次停靠，t[ac]记录停靠时间，f[ac]记录停靠楼层 
				}
				 
		} 
		if(down_to_1==1&&up_to_10==1) break;	
	}
	for(i=1;i<ac;i++)
	printf("%d时，停靠在%d楼",t[ac],f[ac]); 
	return 0; 
}

历史思路（bug之路）

1.从电梯有几种运行路线出发，分为不回头，回头一次，回头两次...结果发现情况太复杂，判断条件太难写，不可实现就舍弃了。
2.从逆向考虑，问题相当于电梯在一楼先载上所有人，然后再逐个卸下。然后最后发现并不能使问题简单化。

待优化：

1.把一些函数从主函数中剥离出来，降低代码的耦合度
2.代码还未完成，有很多bug
3.还未建立git库