电梯调度

一、题目要求

基础大楼一共有四部电梯，每层都有人上下，电梯在每层都停。信1201-1班的张一东觉得在每层都停觉得不耐烦。
由于楼层不太高，在上下课高峰期时时，电梯从一层上行，但只允许停在某一楼层。在一楼时，每个乘客选择自己的目的层，电梯则自动计算出应停的楼层。
问电梯停在那一楼层，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少。

二、设计思路

如果采用遍历的方法，这道题目还是比较容易实现的，这样它的时间复杂度就是N^2。

但是由于这是一个算法优化题所以这样设计：

N0是i-1楼人数，N1是i楼人数,N2是i+1楼人数

Y0是停在i-1楼所有人爬楼数，Y1是停在i楼所有人爬楼数，Y2是停在i+1楼所有人爬楼数，三者之间有这样的关系：

Y0=Y1-（N0-N1-N2）;Y2=Y1-（N2-N0-N1）。

当N0>N1+N2时，Y0<Y1,再比较N0-N1-N2和N2-N0-N1的大小，若前者大则停在i-1层；

当N2>N0+N1时，Y0<Y1,再比较N0-N1-N2和N2-N0-N1的大小，若后者大则停在i+1层；

否则就停在第i层。

三、代码

 1 #include "stdafx.h"
 2 #include <iostream>
 3 using namespace std;
 4 /*自动获取楼层人数*/
 5 void stair(int A[])
 6 {
 7     int length,count;
 8     cout<<"请输入一层时电梯内人数:";
 9     cin>>length;
10     int *a=new int[length];
11     cout<<"请输入每个人所按的楼梯层数:";
12     for(int i=0;i<length;i++)
13     {
14             cin>>a[i];
15             A[a[i]]=A[a[i]]+1;
16     }
17 }
18 int main()
19 {
20      int N = 18;
21      int nPerson[19];
22      int nMinFloor,nTargetFloor;
23      int N1,N2,N3;                        //N1表示当前层以下的人数，N2表示当前层人数，N3表示当前层以上人数
24      nTargetFloor = 1;                    //起始位置为一层
25      /*也可以通过确定每层的人数确定楼层
26      cout<<"请输入到达每层的乘客人数（1-18层）："<<endl;
27       nPerson[0]=0;
28      for(int i=1;i<=N;i++)
29      {
30          cin>>nPerson[i];
31      }*/
32      for(int i=0;i<19;i++)
33      {
34          nPerson[i]=0;
35      }
36      stair(nPerson);
37      N1 = N3 = nMinFloor = 0;
38      N2 = nPerson[1];
39      //得到nTargetFloor等于1时各变量的值
40      for(int i = 2; i <= N; i++)
41      {
42           N3 += nPerson[i];                //当前层以上的人数
43           nMinFloor += nPerson[i] * (i-1);            //总共所需要的楼层数
44      }
45      for(int i=2;i<=N;i++)
46      {
47           if(N1 + N2 < N3)
48           {
49                nTargetFloor = i;                //当前停的楼层数
50                nMinFloor += (N1 + N2 - N3);        //最小楼层数
51                N1 += N2;                        //每次变化楼层，相应楼层人数发生变化
52                N2 = nPerson[i];
53                N3 -= nPerson[i];
54           }
55           else
56           {
57                break;
58           }
59      }
60      cout<<"所停楼层："<<nTargetFloor<<endl;
61      cout<<"最小楼层数："<<nMinFloor<<endl;
62      return 0;
63 }

四、运行截图

五、总结

采用合适的算法可以设计出更高效的程序，单单能实现要求不足以成为一个优秀的程序员，还需努力。