问题描述
假设某机场所有登机口(Gate)呈树形排列(树的度为3),安检处为树的根,如下图所示。图中的分叉结点(编号大于等于100)表示分叉路口,登机口用小于100的编号表示(其一定是一个叶结点)。通过对机场所有出发航班的日志分析,得知每个登机口每天的平均发送旅客流量。作为提升机场服务水平的一个措施,在不改变所有航班相对关系的情况下(即:出发时间不变,原在同一登机口的航班不变),仅改变登机口(例如:将3号登机口改到5号登机口的位置),使得整体旅客到登机口的时间有所减少(即:从安检口到登机口所经过的分叉路口最少)。
编写程序模拟上述登机口的调整,登机口调整规则如下:
- 首先按照由大到小的顺序对输入的登机口流量进行排序,流量相同的按照登机口编号由小到大排序;
- 从上述登机口树的树根开始,按照从上到下(安检口在最上方)、从左到右的顺序,依次放置上面排序后的登机口。
例如上图的树中,若只考虑登机口,则从上到下有三层,第一层从左到右的顺序为:5、6、14、13,第二层从左到右的顺序为:7、8、9、10、1、2、18、17、16、15,第三层从左到右的顺序为:11、12、3、4、20、19。若按规则1排序后流量由大至小的前五个登机口为3、12、16、20、15,则将流量最大的3号登机口调整到最上层且最左边的位置(即:5号登机口的位置),12号调整到6号,16号调整到14号,20号调整到13号,15号调整到第二层最左边的位置(即7号登机口的位置)。
输入
- 首先输入一个整数表示树结点关系的条目数,接着在下一行开始,按层次从根开始依次输入树结点之间的关系。其中分叉结点编号从数字100开始(树根结点编号为100,其它分叉结点编号没有规律但不会重复),登机口为编号小于100的数字(编号没有规律但不会重复,其一定是一个叶结点)。
- 在输入完树结点关系后,接下来输入登机口的流量信息,每个登机口流量信息分占一行,分别包括登机口编号(1~99之间的整数)和流量(大于0的整数),两整数间以一个空格分隔
复制代码
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
3412 100 101 102 103 103 14 108 13 101 5 104 6 104 7 8 -1 102 105 106 107 106 1 110 2 108 16 15 -1 107 18 111 17 110 3 4 -1 105 9 109 10 111 20 19 -1 109 11 12 -1 17 865 5 668 20 3000 13 1020 11 980 8 2202 15 1897 6 1001 14 922 7 2178 19 2189 1 1267 12 3281 2 980 18 1020 10 980 3 1876 9 1197 16 980 4 576
输出
按照上述调整规则中排序后的顺序(即按旅客流量由大到小,流量相同的按照登机口编号由小到大)依次分行输出每个登机口的调整结果:先输出调整前的登机口编号,再输出要调整到的登机口编号。编号间均以一个空格分隔。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2212 5 20 6 8 14 19 13 7 7 15 8 3 9 1 10 9 1 13 2 18 18 6 17 2 16 10 15 11 11 16 12 14 3 17 4 5 20 4 19
问题分析
虽然题面上说是树,但想到有层次关系,很容易就能想到用宽搜bfs
C++
复制代码
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#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 1010, M = 110; vector<int> tree[1010]; // 存储分支结点 vector<int> ans; // 按规则次序存储登机口,左右上下 int n, m; queue<PII> q; struct Door { int no; // 编号 int man; // 人流量 bool operator<(const Door& W) const { if (man == W.man) return no < W.no; return man > W.man; } }door[M]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); for (int j = 0; j < 3; j++) { int y; scanf("%d", &y); if (y != -1) tree[x].push_back(y); } } q.push({100, 0}); while (q.size()) { auto t = q.front(); q.pop(); int num = t.first, level = t.second; for (auto tmp: tree[num]) { if (tmp >= 100) { q.push({tmp, level+1}); } else { ans.push_back(tmp); } } } m = ans.size(); for (int i = 0; i < m; i++) { scanf("%d %d", &door[i].no, &door[i].man); } sort(door, door + m); for (int i = 0; i < m; i++) { printf("%d %dn", door[i].no, ans[i]); } return 0; }
最后
以上就是发嗲大山最近收集整理的关于【buaa机试题】机场登机口调整的全部内容,更多相关【buaa机试题】机场登机口调整内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复