设有如下图所示的火车车轨,入口到出口之间有n条轨道,列车的行进方向均为从左至右,列车可驶入任意一条轨道。现有编号为1~9的9列列车,驶入的次序依次是8,4,2,5,3,9,1,6,7。若期望驶出的次序依次为1~9,则n至少是( )。

admin2017-08-16  32

问题 设有如下图所示的火车车轨,入口到出口之间有n条轨道,列车的行进方向均为从左至右,列车可驶入任意一条轨道。现有编号为1~9的9列列车,驶入的次序依次是8,4,2,5,3,9,1,6,7。若期望驶出的次序依次为1~9,则n至少是(          )。

选项 A、2
B、3
C、4
D、5

答案C

解析 在确保队列先进先出原则的前提下。根据题意具体分析:入队顺序为8,4,2,5,3,9,1,6,7,出队顺序为1.9。入口和出口之间有多个队列(n条轨道),且每个队列(轨道)可容纳多个元素(多列列车)。如此分析:显然先入队的元素必须小于后入队的元素(如果8和4入同队列,8在前4在后,那么出队时只能是8在前4在后),这样8入队列1,4入队列2,2入队列3,5入队列2(按照前面的原则“大的元素在小的元素后面”也可以将5入队列3,但这时剩下的元素3就必须放到一个新的队列里面,  无法确保“至少”,本应该是将5入队列2,再将3入队列3,不增加新队列的情况下,可以满足题意“至少”的要求),3入队列3,9入队列1,这时共占了3个队列。后面还有元素1,直接再占用一个新的队列4,1从以列4出队后,剩下的元素6和7或者入队到队列2或者入队到队列3(为简单起见我们不的设n个队列的序分别1,2,…,n),这样满足题目的要求。综上,共占用了4个队列。当然还有其他的入队出队的情况,请考生们自行推演。但要确保满足:1)队列中后面的元素大于前面的元素;2)确保占用最少(即满足题目中的“至少”)的队列。
转载请注明原文地址:https://jikaoti.com/ti/LifjFFFM
0

相关试题推荐
最新回复(0)