腾讯面试题 电梯最佳调度

缘起

相信每个有点自负的程序员在写字楼里面等电梯的时候都会有想过电梯的调度算法.

1
2
3
4
5
6
7
8
9
10
11
12
腾讯面试题

问题如下:

    一座楼里没有楼梯，只有一架电梯，
    电梯一次最多只能乘3人，
    已知楼共有20层，每层有一个人，
    每个人都有1~20中唯一的编号，他们要去对应的楼层。
    电梯初始状态：在一楼。
    目标状态：每个人在相应楼层。

试编写一个算法，完成目标状态，而且使电梯移动最小距离。

我知道此题是因为 腾讯笔试题电梯问题思路和初步的算法_討論一下 [问题点数：20分，结帖人zhanzongru]

这里的炒鸡热闹的讨论.

分析

此题考查的其实是操作系统的磁盘调度的电梯算法.

1
2
3
4
5
6
比如磁道号从41开始，磁盘请求序列为:20 44 40 4 80 12 76。该怎么移动呢?
答:就是读取时按找当前的移动方向读取下一个，到顶后再反着读，就跟坐电梯一样，要不先上，要不先下。
假设当前磁头移动方向是向下. 
下：40 20 12 4 上： 44 76 80
合起来就是： 40 20 12 4 44 76 80
这样的话磁头的总移动距离会相对减少

所以就很好模拟了~ 唯一和上面举的磁盘调度算法例子不一样的地方在于最多乘坐三人怎么办? 很好办啊~ 如果电梯是向上的话，就优先将标号最大的人送到顶. 如果是电梯是向下的话, 就优先将标号最小的送到底. 于是就必须要使用一个数据结构来模拟电梯的轿厢. 大小为3的堆就再合适不过了~ 因为向上是求当前最大的3个标号. 所以用大小为3的小根堆模拟向上电梯即可. 因为向下是求当前最小的三个标号, 所以用大小为3的大根堆模拟向下电梯即可. 最后如何知道电梯已经不需要向上以及所有人都归位了呢? 注意到20这个数据规模比较小. 所以我们可以使用二进制压缩一开始所有的需要向上的人的状态和所有需要向下的人的状态, 也就是下面代码中的 remain_up和remain_down.

先上代码（以下代码在vs2010中调试通过.）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include "stdafx.h"

#include <stdio.h>
#include <queue>
using namespace std;
#define LOCAL

const int maxn = 25; // 电梯最多20层
int n,a[maxn],b[maxn], remain_up, remain_down, ans, pos, dir; // remain_up是剩下还需要向上的人,remain_down是剩下还需要向下的人,pos是电梯的位置, dir是电梯运行的方向, 1表示向上,0表示向下

priority_queue<int,vector<int>,greater<int> > pq_up; // 向上的电梯(小根堆)
priority_queue<int,vector<int>,less<int> > pq_down; // 向下的电梯(大根堆)

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d", &n))
	{
		ans = remain_up = remain_down = pos = 0,dir = 1;
		for (int i = 1; i<=n;i++)
		{
			scanf("%d", a+i);
			b[i] = a[i]; // a记录的是向上的人, b记录的是向下的人
			if (a[i]>i) // i层本来应该有的人是i,但是现在是a[i]>i, 比如3层是16, 则a[i]=16自然要向上
			{
				remain_up |= 1<<a[i]-1;
			}
			else if (a[i]<i)
			{
				remain_down |= 1<<a[i]-1;
			}
		} // a[i]表示层i的人的编号
		bool flag = false;
		while(remain_up || remain_down) // 只要还有人没有归位(不论是向上归位还是向下归位),电梯就要移动
		{
			if (dir) // 如果是向上的电梯
			{
				pos++;
				while(pos<=n) // 电梯移动到pos层准备卸人或者装人
				{
					int t = a[pos]; // 保存原值
					if (!(remain_up & (((1<<n)-1) & ~((1<<pos-1)-1)))) // 如果pos位置之后再无需要向上归位的人了
					{
						break;
					}
					if (!pq_up.empty())
					{
						int top = pq_up.top(); // 每移动一个位置, 就要考察堆中元素有无到达合适位置
						if (top==pos) // 如果归位了
						{
							printf("%d到了%d层, %d出电梯.\n", top, pos, top);
							a[pos] = top;
							remain_up &= ~(1<<top-1); // 少了一个没向上归位的人
							pq_up.pop();
						}
					}
					if (t>pos) // 碰到个要向上的人
					{
						if (pq_up.size()==3) // 如果电梯满了
						{
							int top = pq_up.top();
							if (top<t)
							{
								pq_up.pop();
								pq_up.push(t); // 堆中存放的都是人的编号
								printf("%d在%d层进入了电梯.\n", t, pos);
								if (top==pos) // 如果pos刚好是top想去的楼层的话
								{
									remain_up &= ~(1<<top-1); // 少了一个没向上归位的人
								}
								else
								{
									a[pos] = top; // top没到心仪的楼层就提前(在pos层)下电梯了
								}
								printf("%d到了%d层, %d出电梯.\n", top, pos, top);
							}
						}
						else
						{
							pq_up.push(t); // 没满的话, 尽管往里塞
							a[pos] = 0; // 则下次向上的时候, 此楼层的人就不会再进电梯(即pq_up)了
							printf("%d在%d层进入了电梯.\n", t,pos);
						}
					}
					pos++;
					if (pos<=n)
					{
						ans++; // 电梯向上移动一格
						printf("电梯从%d层移动到了%d层\n\n", pos-1, pos);
					}
				}
			}
			else // 电梯向下运动,来到pos位置处
			{
				pos--;
				while(pos)
				{
					int t = b[pos]; // 保存原值
					if (!(remain_down & ((1<<pos)-1))) // 如果 pos以前都没有
					{
						break;
					}
					if (!pq_down.empty())
					{
						int top = pq_down.top(); // 每移动一个位置, 就要考察堆中元素有无到达合适位置
						if (top==pos) // 如果归位了
						{
							printf("%d到了%d层, %d出电梯.\n", top, pos, top);
							b[pos] = top;
							remain_down &= ~(1<<top-1); // 少了一个没向下归位的人
							pq_down.pop();
						}
					}
					if (t<pos)  // 碰到个要向下的人
					{
						if (pq_down.size()==3)
						{
							int top = pq_down.top();
							if (top>t)
							{
								pq_down.pop();
								pq_down.push(b[pos]);
								printf("%d在%d层进入了电梯.\n", t, pos);
								if (top==pos) 
								{
									remain_down &= ~(1<<top-1);
								}
								else
								{
									b[pos] = top; 
								}
								printf("%d到了%d层, %d出电梯.\n", top, pos, top);
							}
						}
						else
						{
							pq_down.push(t); 
							b[pos] = maxn;
							printf("%d在%d层进入了电梯.\n", t,pos);
						}
					}
					pos--;
					if (pos)
					{
						ans++; 
						printf("电梯从%d层移动到了%d层\n\n", pos+1, pos);
					}
				}
			}
			dir = 1-dir; // 完成向上, 反向
		}
		printf("电梯最少移动层数为%d层.\n", ans);
	}
	return 0;
}

核心代码其实很少——模拟单方向的电梯运动只有60行.

先看一下效果吧~ 例如测试数据如下

1
2
20
6 19 17 12 10 15 3 13 7 8 4 20 9 2 14 18 11 5 1 16

即20个人, 程序运行结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
6在1层进入了电梯.
电梯从1层移动到了2层

19在2层进入了电梯.
电梯从2层移动到了3层

17在3层进入了电梯.
电梯从3层移动到了4层

12在4层进入了电梯.
6到了4层, 6出电梯.
电梯从4层移动到了5层

电梯从5层移动到了6层

15在6层进入了电梯.
12到了6层, 12出电梯.
电梯从6层移动到了7层

电梯从7层移动到了8层

电梯从8层移动到了9层

电梯从9层移动到了10层

电梯从10层移动到了11层

电梯从11层移动到了12层

20在12层进入了电梯.
15到了12层, 15出电梯.
电梯从12层移动到了13层

电梯从13层移动到了14层

电梯从14层移动到了15层

电梯从15层移动到了16层

18在16层进入了电梯.
17到了16层, 17出电梯.
电梯从16层移动到了17层

电梯从17层移动到了18层

18到了18层, 18出电梯.
电梯从18层移动到了19层

19到了19层, 19出电梯.
电梯从19层移动到了20层

20到了20层, 20出电梯.
16在20层进入了电梯.
电梯从20层移动到了19层

1在19层进入了电梯.
电梯从19层移动到了18层

5在18层进入了电梯.
电梯从18层移动到了17层

11在17层进入了电梯.
16到了17层, 16出电梯.
电梯从17层移动到了16层

电梯从16层移动到了15层

电梯从15层移动到了14层

2在14层进入了电梯.
11到了14层, 11出电梯.
电梯从14层移动到了13层

电梯从13层移动到了12层

电梯从12层移动到了11层

4在11层进入了电梯.
5到了11层, 5出电梯.
电梯从11层移动到了10层

电梯从10层移动到了9层

电梯从9层移动到了8层

电梯从8层移动到了7层

3在7层进入了电梯.
4到了7层, 4出电梯.
电梯从7层移动到了6层

电梯从6层移动到了5层

电梯从5层移动到了4层

电梯从4层移动到了3层

3到了3层, 3出电梯.
电梯从3层移动到了2层

2到了2层, 2出电梯.
电梯从2层移动到了1层

1到了1层, 1出电梯.
电梯从1层移动到了2层

电梯从2层移动到了3层

电梯从3层移动到了4层

6在4层进入了电梯.
电梯从4层移动到了5层

10在5层进入了电梯.
电梯从5层移动到了6层

6到了6层, 6出电梯.
12在6层进入了电梯.
电梯从6层移动到了7层

电梯从7层移动到了8层

13在8层进入了电梯.
电梯从8层移动到了9层

电梯从9层移动到了10层

10到了10层, 10出电梯.
电梯从10层移动到了11层

电梯从11层移动到了12层

12到了12层, 12出电梯.
15在12层进入了电梯.
电梯从12层移动到了13层

13到了13层, 13出电梯.
电梯从13层移动到了14层

电梯从14层移动到了15层

15到了15层, 15出电梯.
电梯从15层移动到了16层

17在16层进入了电梯.
电梯从16层移动到了17层

17到了17层, 17出电梯.
电梯从17层移动到了18层

16在17层进入了电梯.
电梯从17层移动到了16层

16到了16层, 16出电梯.
电梯从16层移动到了15层

14在15层进入了电梯.
电梯从15层移动到了14层

14到了14层, 14出电梯.
11在14层进入了电梯.
电梯从14层移动到了13层

9在13层进入了电梯.
电梯从13层移动到了12层

电梯从12层移动到了11层

11到了11层, 11出电梯.
5在11层进入了电梯.
电梯从11层移动到了10层

8在10层进入了电梯.
电梯从10层移动到了9层

9到了9层, 9出电梯.
7在9层进入了电梯.
电梯从9层移动到了8层

8到了8层, 8出电梯.
电梯从8层移动到了7层

7到了7层, 7出电梯.
4在7层进入了电梯.
电梯从7层移动到了6层

电梯从6层移动到了5层

5到了5层, 5出电梯.
电梯从5层移动到了4层

4到了4层, 4出电梯.
电梯从4层移动到了3层

电梯最少移动层数为69层.

再简单证明一下上述算法是正确的.

令 Up={i: a[i]>i}, Down={i: a[i]<i}, 则Up是伊始需要向上走的人的集合（其实就记录在上面代码中的a数组中了, 操作a就是在操作这部分人）. 而Down是伊始需要向下走的人的集合（其实就记录在上面代码中的b数组中了, 操作b就是在操作这部分人）.

电梯的运动一定是上->下->上->下->….->上->下的（因为伊始在第一层）.

如果向上你不上到顶的话, 而只是上到x层，即不让 Up中最大的三个元素归位的话, 则下次你还是要上到顶. 那样的话, 将白白耗费2*(n-x)的距离. 这就不是最优的了.

注意，思想是简单的. 但是代码实现起来还是比较细节化的.程序中大量使用位运算便于状态的判断而不是低效的遍历——例如判断是否还有向上（下）的人没有归位.

而且阅读完上面的代码的人就发现，其实本质上的问题就是伊始需要向上的人和伊始需要向下的人的整体向上和向下的迁徙. 只是因为轿厢至多乘坐3个人所以有些在轿厢中的人虽然未到目的地但是也不得不提早下电梯. 等待下一次向上或向下的电梯. 例如二层向上的电梯里面有7,8,11 三个人，他们显然想去的是7,8,11层, 但是上到第5层的时候，来了个19， 则19想去19层. 而19是优先的（因为19大啊~）则7,8,11中必定有一个人要腾出位置. 这个人就是电梯中最小的那个——7(这种过程就是使用堆这种数据结构来模拟最好). 即7不得不遗憾的在第5层下电梯. 19上电梯. 然后电梯载着8,11,19三个人继续向上.

上述程序其实就是在模拟这个过程.

挺开心的~ 毕竟数据结构和算法在实际生活（虽然有人吐槽此题还不够贴近实际QAQ）中用到了一次~