题目总结摘要：假设某机场所有登机口（Gate）呈树形排列（树的度为 3），安检处为树的根，如下图所示。图中的分叉结点（编号大于等于 100）表示分叉路口，登机口用小于 100的编号表示（其一定是一个叶结点）。通过对机场所有出发航班的日志分析，得知每个登机口每天的平均发送旅客
考察的知识点主要有排序、广度优先搜索、初等数论、链表、模拟等。
题目详解机场登机口调整模拟
问题描述
假设某机场所有登机口（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的数字（编号没有规律但不会重复，其一定是一个叶结点）。树中结点间关系用下面方式描述：
R S1 S2 S3
其中 R为分叉结点，从左至右 S1,S2,S3分别为树叉 R的子结点，其可为树叉或登机口，由于树的度为 3，S1,S2,S3中至多可以 2个为空，该项为空时用 -1 表示。
如：100 101 102 103表明编号 100的树根有三个子叉，编号分别为 101、102和 103。
又如：104 7 8 -1 表明树叉 104上有 2个编号分别为 7和 8的登机口。
假设分叉结点数不超过 100个。
分叉结点输入的顺序不确定，但可以确定：输入某个分叉结点信息时，其父结点的信息已经输入。
在输入完树结点关系后，接下来输入登机口的流量信息，每个登机口流量信息分占一行，分别包括登机口编号（ 1∼99之间的整数）和流量（大于 0的整数），两整数间以一个空格分隔。
输出描述
按照上述调整规则中排序后的顺序（即按旅客流量由大到小，流量相同的按照登机口编号由小到大）依次分行输出每个登机口的调整结果：先输出调整前的登机口编号，再输出要调整到的登机口编号。编号间均以一个空格分隔。数据范围
分叉结点数量 [1,100]，分叉结点编号不超过 300。
登机口数量 [1,99]，
流量数据范围 [1,10000]
示例
输入12
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
输出
12 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
思考
题目很长，但是理解了之后，其实能发现主要考察得就是排序和广度优先搜索算法。首先第一步就是建图（也可以理解成3叉树），按照邻接表的方式建图。
第二步是对所有的登机口进行排序，可以自定义排序规则，然后直接用库函数排序。
第三步是从入口处开始广度优先遍历图，碰到叶子结点的时候输出对应的排序后的相应元素。
代码
#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusingstd::vector;usingstd::string;structPort{intid;inttraffic;};boolcmp(Portp1,Portp2){if(p1.traffic!=p2.traffic){returnp1.traffic>p2.traffic;}returnp1.id>n;std::vector>graph(301);for(inti=0;i>a>>b>>c>>d;if(b!=-1){graph[a].push_back(b);}if(c!=-1){graph[a].push_back(c);}if(d!=-1){graph[a].push_back(d);}}intid,traffic;std::vectorv;while(std::cin>>id>>traffic){v.push_back({id,traffic});}std::sort(v.begin,v.end,cmp);std::queueq;q.push(100);inti=0;while(!q.empty){inttop=q.front;q.pop;if(graph[top].empty){std::cout
连续合数段
问题描述
给定区间 [a,b]，输出这个区间里最长的连续合数段。一行，两个整数a,b输出描述
一行，输出最长的连续合数段。如果答案不唯一，则输出首项最小的那一段。
示例
输入1 10
输出
8 9 10
思考
遍历[a,b]范围内的所有数，利用试除法判断一个数是否为合数，由此枚举出最长的连续合数段。代码
#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusingstd::vector;usingstd::string;boolisPrime(intx){if(x==1){returnfalse;}if(x==2||x==3){returntrue;}for(inti=2;i*i>a>>b;intmaxLen=0,start=0;for(inti=std::max(2,a);imaxLen){maxLen=cnt;start=i-cnt;}}else{++i;}}for(inti=start;i空闲块
问题描述
在操作系统中，空闲存储空间通常以空闲块链表方式组织，每个块包含块起始位置、块长度及一个指向下一块的指针。空闲块按照存储位置升序组织，最后一块指向第一块（构成循环链表）。
当有空间申请请求时，按照如下原则在空闲块循环链表中寻找并分配空闲块：
从当前位置开始遍历空闲块链表（初始是从地址最小的第一个空闲块开始），寻找满足条件的最小块（即：大于等于请求空间的最小空闲块，如果有多个大小相同的最小空闲块，则选择遍历遇到的第一个最小空闲块）（最佳适应原则）；如果选择的空闲块恰好与请求的大小相符合，则将它从链表中移除并返回给用户；这时当前位置变为移除的空闲块指向的下一空闲块；如果选择的空闲块大于所申请的空间大小，则将大小合适的空闲块返回给用户，剩下的部分留在空闲块链表中，且剩下位置的起始地址不变；这时当前位置仍然为该空闲块；如果找不到足够大的空闲块，则申请失败；这时当前位置不变。
例如：下图示例给出了空闲块链表的初始状态，每个结点表示一个空闲块，结点中上面的数字指空闲块的起始位置，下面的数字指空闲块的长度，位置和长度都用正整数表示，大小不超过 int 表示范围。
当前位置为最小地址为 1024的空闲块。
则从当前位置开始遍历上图的链表，按照上述原则寻找到满足条件的最小块为地址是 16384的空闲块，其长度正好为 1024，所以将其从链表中删除，这时链表状态如下图所示，当前位置变成地址为 32768的空闲块。
下面继续为第四个空间请求（大小为 512）遍历链表，按照上述原则寻找到满足条件的最小块为当前位置的空闲块，其长度等于请求的空间大小，于是将该空闲块删除后，链表状态变为下图所示：
接下来 N行，每行包含两个正整数，按照起始位置由小到大的顺序依次描述每个空闲块的起始位置和长度。
最后一行包含若干正整数，按照申请的先后顺序依次描述每个申请的空间大小，最后以一个 -1 表示结束。
输出格式
按照上述原则模拟完空闲空间申请后，输出当前空闲空间链表状态，即从当前位置开始，遍历链表，分行输出剩余空闲块的起始位置和长度，位置和长度之间以一个空格分隔。若申请完后，链表中没有空闲块，则什么都不输出。
示例
输入12
1024 2048
8192 512
16384 1024
32768 8192
65536 8192
77824 1024
80896 3072
86016 1024
91136 5120
99328 512
104448 1024
112640 3072
1024 2560 10240 512 1024 6400 512 -1
输出
104448 1024
112640 3072
1024 2048
8192 512
32768 1792
65536 8192
77824 1024
91136 5120
思考
用链表进行模拟，对应c++的STL的话，可以用list模拟。代码
#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusingstd::vector;usingstd::string;structBlock{intaddr;intsize;};voidsolve{intn;std::cin>>n;std::listli;for(inti=0;i>b.addr>>b.size;li.push_back(b);}intreq;std::list::iteratorit=li.begin;while(std::cin>>req){if(req==-1){break;}std::list::iteratormin=it;for(inti=0;isize>=req){if(min->sizesize>it->size){min=it;}}it++;if(it==li.end){it=li.begin;}}it=min;if(min->size>=req){if(min->size==req){it=li.erase(it);n--;}else{it->size-=req;}}}for(inti=0;iaddrsize来源：天哥教育
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!