设有下图所示的火车车轨,入口到出口之间有 n 条轨道,列车的行进方向均为从左至右,列车可驶入任意一条轨道。现有编号为1~9的9列列车,驶入的次序依次是8, 4, 2, 5, 3, 9, 1, 6, 7。若期望驶出的次序依次为1~9,则 n 至少是( )。
A. 2
B. 3
C. 4
D. 5
列车可驶入任意一条轨道,一夫多妻。
队列,先进先出,需要求最少的队列数,那就尽可能一个队列多放元素。
入队次序8->4->2->5->3->9->1->6->7
出队次序9-8-7-6-5-4-3-2-1(元素依次递减,那么说明我们在入队时考虑队中已经存在的元素都比该元素大就可以啦~没搞明白好好想想)
第一辆列车8:创立第一个队列,放入
【1】8
列车4:比8小,放在8的那个队列
【1】4->8
列车2:比4小,那就放在4的这个队列
【1】2->4->8
列车5:比2大,不能放在这个队列,因为同一队列先进先出,放在这里不能得到5在2的前面,故而创立队列2,并放入队列2
【2】5
列车3:比2大,跳过队列1,比5小,放入队列2
【2】3->5
列车9:比2,3都大,创立队列3,并放入
【3】9
列车1:比2小,放入队列1
【1】1->2->4->8
列车6:比9小,放入队列3
【3】6->9
列车7:比1,3,6都大,创立队列4,并放入
【4】7
最后根据出队次序[3][1][4][3][2][1][2][1][1]即可得到9~1的驶出序列
--> 42 -->
--> 53 -->
--> 961 --> --> 87 -->
队列为先进先出,这里要求出队顺序为...
用户登录可进行刷题及查看答案
队列为先进先出,这里要求出队顺序为1~9,相当于利用多个队列作为归并段,然后多路归并成一个有序数组,每个归并段单调递增。题目要求 n 最少,所以采用贪心策略,尽量少创建队列,我们很容易模拟出这个过程:
很明显,最后有4个队列(归并段)。
当然,这个答案不唯一,我是按照从上到下的方式选择入队队列,也可以按照别的顺序选择,但是必须要求每个队列队头到队尾升序排序。
最后一步归并排序也很简单,每次选择所有队列中最小的队头元素出队。
本题选C。
登录后提交答案