题16

题16

题目

[!question]+
【2016 统考真题】设有如下图所示的火车车轨,入口和出口之间有 条轨道,列车的行进方向均为从左至右,列车可驶入任意一条轨道.
现有编号为 的 9 列列车,驶入的次序依次是 .
若期望驶出的次序依次为 ,则 至少是 ( ) .

A. 2
B. 3
C. 4
D. 5

分析

[!NOTE]+
这像是一个排序的问题，就是使用某种以栈或者队列为结构的排序算法，把输入的数列排序到输出序列，最少需要多少次操作

这个题目应该看成是，多个输入端口，一个输出端口的双端队列模型的扩展

解

[!done]+
C
根据题意: 入队顺序为 8,4,2,5,3,9,1,6,7 ,出队顺序为 1 ~ 9 。
入口和出口之间有多个队列 ( n 条轨道),且每个队列 (轨道) 可容纳多个元素 (多列列车),为便于区分,队列用字母编号。
分析如下: 显然先入队的元素必须小于后入队的元素 (否则, 若 8 和 4 入同一个队列, 8 在 4 前面,则出队时也只能 8 在 4 前面),这样 8 入队列 A, 4 入队列 B, 2 入队列 C, 5 入队列 B (按照前述原则 “大的元素在小的元素后面” 也可将 5 入队列 C, 但这时剩下的元素 3 就必须放入一个新的队列中, 无法确保 “至少”), 3 入队列 C, 9 入队列 A, 这时共占了 3 个队列, 后面还有元素 1, 直接再用一个新的队列 D, 1 从队列 D 出队后, 剩下的元素 6 和 7 或入队列 B, 或入队列 C 。综上,共占用了 4 个队列。
当然还有其他的入队、出队情况,请读者自己推演,但要确保满足:
①队列中后面的元素大于前面的元素;
②确保占用最少 (即满足题意中 “至少”) 的队列。