返回主页
[数据结构 P2043] 设有下图所示的火车车轨，入口到出口之间有 n 条轨道，列车的行进方向均为从左至右，列车可驶入任意一条
未通过
设有下图所示的火车车轨，入口到出口之间有 n 条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1~9的9列列车，驶入的次序依次是8, 4, 2, 5, 3, 9, 1, 6, 7。若期望驶出的次序依次为1~9，则 n 至少是（ ）。
A. 2
B. 3
C. 4
D. 5
上面问题的答案是：
加入错题本
个人笔记
队列为先进先出，这里要求出队顺序为...
用户登录可进行刷题及查看答案
队列为先进先出，这里要求出队顺序为1~9，相当于利用多个队列作为归并段，然后多路归并成一个有序数组，每个归并段单调递增。题目要求 n 最少，所以采用贪心策略，尽量少创建队列，我们很容易模拟出这个过程：
很明显，最后有4个队列（归并段）。
当然，这个答案不唯一，我是按照从上到下的方式选择入队队列，也可以按照别的顺序选择，但是必须要求每个队列队头到队尾升序排序。
最后一步归并排序也很简单，每次选择所有队列中最小的队头元素出队。
本题选C。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案
暂无评论，来抢沙发