题目

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

结构（文字版）：入口在左、出口在右，中间是 n 条平行轨道。所有列车均从入口进入，从出口驶出，方向全程"从左至右"——一旦驶入某条轨道就只能向右走，不能在轨道内调头或后退。每条轨道都是 FIFO 队列：早进入轨道的列车必先出去。

错因

A

误以为 2 条轨道够用，可能把"轨道"想成了栈（后进先出）。如果是栈，先入的 8 可以一直压在底，后续的 4, 2 压在它上面，再 LIFO 出。但题目里轨道是单向通道，列车进出方向相同，只能 FIFO，不是 LIFO。栈和队列在这道题里给出的最少条数完全不同（事实上 9 列车的输入若用栈，需要的栈数也远多于 2）。

B

算到一半漏处理了 1。前 6 辆 8, 4, 2, 5, 3, 9 用 3 条轨道恰好够用：Q1=[8, 9]、Q2=[4, 5]、Q3=[2, 3]。但第 7 辆是 1，比所有现存队列的队尾（9, 5, 3）都小——若把 1 接到任意一条队列后面，那条队列的出场顺序就不再单调递增，必然违反"按 1~9 输出"的约束。所以必须新开第 4 条轨道装 1。选 B 的人很可能是在最后一辆没仔细对照 1 的位置就交卷。

D

多开了一条不必要的轨道。常见误算路径是：处理到 6 时认为没有合适队列可以接，新开了一条 [6]；接着 7 也跟不上，又跑去新开。但实际上 6 可以接到 Q2 = [4, 5] 的尾部（5 < 6 ✓），7 又可以接到 Q2 = [4, 5, 6] 的尾部（6 < 7 ✓）。选 D 的人没贯彻"贪心：尽量塞进已有队列的最大队尾"的策略，遇到稍棘手的就开新轨道。

总解析

关键观察：每条轨道是 FIFO 队列，队列里的列车出场顺序 = 进入顺序。要让所有列车按 1, 2, …, 9 的顺序出场，每条轨道里的列车编号必须从队头到队尾严格递增——否则后入的先出就矛盾了。

贪心策略：处理输入序列里的每辆车 x，放进"队尾最大但仍 ≤ x"的那条轨道；若所有队尾都 > x，必须新开一条轨道。

输入次序：8, 4, 2, 5, 3, 9, 1, 6, 7。

步	来车	各轨道队尾	决策	各轨道状态
1	8	—	新开 Q1	Q1=[8]
2	4		没有 ≤ 4 的，新开 Q2	Q1=[8], Q2=[4]
3	2		没有 ≤ 2 的，新开 Q3	Q1=[8], Q2=[4], Q3=[2]
4	5		4 ≤ 5（最大），接 Q2	Q2=[4, 5]
5	3		2 ≤ 3，接 Q3	Q3=[2, 3]
6	9		8 ≤ 9，接 Q1	Q1=[8, 9]
7	1		全 > 1，新开 Q4	Q4=[1]
8	6		5 ≤ 6，接 Q2	Q2=[4, 5, 6]
9	7		6 ≤ 7，接 Q2	Q2=[4, 5, 6, 7]

最终 4 条轨道：

Q1: 8 → 9
Q2: 4 → 5 → 6 → 7
Q3: 2 → 3
Q4: 1

每条队列内编号都递增，9 辆车全部安置完毕。

为什么 1 一定要单独一条？ 1 比任何已入轨的车都小，强行接到任何已有队列后面都会让那条队列的"队尾大、队头小"——出车时就先出大的、后出小的，违反 1~9 顺序。

为什么 4 条够用、不需要更多？ 上面的贪心给出了一种 4 条的可行方案，证明 ≤ 4 够用；步 7 又证明 < 4 不行。两边夹住，最少是 4。

最终答案是 C（4）。