课堂练习之电梯调度

一、题目：电梯调度

二、要求

1、在一楼，每个乘客选择自己的目的层，电梯则自动计算出应停的楼层

2、电梯停在哪一楼层，能够保证乘坐电梯的所有乘客爬楼梯的层数之和最少

三、解题思路

假设电梯停在i层，我们可以计算出所有乘客总共需要爬楼梯的层数Y。

　　假设有N1个乘客在i层楼以下，N2个乘客在第i层楼，还有N3个乘客在第i层楼以上。

　　这个时候，如果电梯改停在i-1层，所有目的地在第i层及以上的乘客都需要多爬一层，即N2+N3层，而所有目的地在i-1层及以下的乘客可以少爬一层，总共可以少爬N1层。

　　因此，乘客总共需要爬的层数为Y-N1+N2+N3 = Y-(N1-N2-N3)层。

　　反之，如果电梯在i+1层停，则总共需要爬的层数为Y+(N1+N2-N3)层。

　　由此可见：

　　当N1 > N2 + N3时，i-1层比i层好；

　　当N1 + N2 < N3时，i+1层比i层好。

四、程序源码

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main(int argc, char* argv[])
 5 {
 6     int N = 0,i;
 7     int nPerson[100];
 8     int nMinFloor, nTargetFloor;
 9     int N1, N2, N3;
10 
11     cout<<"请输入总的楼层数:";
12     
13     while(cin>>N) //输入总的楼层
14     {
15         //输入到每一层的人的个数
16         for(i = 0; i < N; ++i)
17         {
18             cout<<"请输入到第"<<i+1<<"层的人数:";
19             cin >> nPerson[i];
20             cout<<endl;
21         }
22 
23         //进行状态清零
24         nTargetFloor = 0;
25         nMinFloor = 0;
26 
27         N1 = 0; 
28         N2 = nPerson[0];
29         N3 = 0;
30 
31         for (i = 1; i < N; ++i)
32         {
33             N3 += nPerson[i];
34             nMinFloor += nPerson[i] * (i - 1);
35         }
36 
37         for(i = 1; i < N; ++i)
38         {
39             if(N1 + N2 < N3)
40             {
41                 nTargetFloor = i;
42                 nMinFloor +=(N1 + N2 - N3);
43 
44                 N1 += N2;
45                 N2 = nPerson[i];
46                 N3 -= N2;
47             }
48             else
49             {
50                 //否则第i层的结果已经最小，故不需要计算第i+1层 
51                 break;
52             }
53         }
54 
55 
56 
57         //输出计算结果
58         cout << "The best floor is:  " << nTargetFloor + 1 << endl;
59 
60     }
61 
62     return 0;
63 }

五、实验截图

六、总结

通过本次试验，了解和学习了电梯最优的情况和相应的算法，根据程序更加深刻的理解每一个问题，在今后学习中会对自己有很大的帮助。

课堂练习之电梯调度

推荐阅读