PTA 7-4 列车调度题解：不用队列，一个数组搞定（C语言版，含时间复杂度分析）

PTA 7-4 列车调度：用数组实现的高效解法与思维突破

当面对PTA 7-4列车调度这类算法题时，大多数初学者会条件反射地想到栈或队列这类数据结构。但真正高效的解法往往来自对问题本质的洞察——在这个案例中，我们只需要统计所需轨道数量，而不必完整模拟列车入轨过程。这种思维转换不仅能大幅简化代码，还能显著提升性能。

1. 问题重述与常规解法分析

题目要求将一列编号无序的列车调度到若干轨道上，每条轨道上的列车编号必须保持递增顺序。例如输入序列为[8, 4, 2, 5, 3, 9, 1, 6, 7]时，最少需要4条轨道：

轨道1: 1 → 3 → 5 → 8 → 9 轨道2: 2 → 6 → 7 轨道3: 4 轨道4: (空)

常规队列解法的思路是：

1. 为每列新到达的列车寻找第一条可以停靠的轨道（即轨道末尾编号小于当前列车）
2. 若无合适轨道，则新增一条
3. 最终统计使用的轨道总数

这种解法时间复杂度为O(n²)，当n较大时（如PTA测试用例中的10^5规模），很容易超时。更关键的是，它完整模拟了调度过程，而实际上我们只需要知道最少轨道数。

2. 数组解法的核心思路

突破点在于认识到：我们只需要维护每条轨道上的最后一列车的编号。具体来说：

• 用数组note记录各轨道当前最后一列车的编号
• 数组长度num即为当前使用的轨道数
• 对于新列车x，只需确定它应该接在哪条轨道后面

这种思路将问题转化为：维护一个有序数组，使得每个新元素都能找到合适的插入位置。这与最长递增子序列(LIS)问题的解法有异曲同工之妙。

3. 优化实现的关键步骤

以下是经过优化的C语言实现核心逻辑：

int note[MAX_SIZE] = {0}; int num = 0; for(int i = 0; i < n; i++) { scanf("%d", &x); if(i == 0) { note[num++] = x; continue; } if(x > note[num-1]) { // 需要新轨道 note[num++] = x; } else if(x < note[0]) { // 可以接在最小轨道前 note[0] = x; } else { // 二分查找插入位置 int left = 0, right = num-1; while(left < right) { int mid = left + (right-left)/2; if(note[mid] < x) { left = mid + 1; } else { right = mid; } } note[left] = x; } }

三个关键处理分支：

1. x > note[num-1]：当前列车编号大于所有轨道末尾，必须新增轨道
2. x < note[0]：可以接在最小编号轨道前，更新最小值
3. 其他情况：通过二分查找确定插入位置

4. 时间复杂度分析与对比

让我们对比两种解法的时间复杂度：

为何能避免排序：

• 原代码中注释掉的qsort是不必要的，因为数组本身已经保持有序
• 通过精心设计的插入逻辑，我们隐式维护了数组的有序性
• 每次更新都确保不会破坏note[0]最小、note[num-1]最大的性质

5. 实际编码中的常见陷阱

在实现这个算法时，有几个容易出错的地方值得注意：

1. 数组越界：PTA测试用例中n可达10^5，确保数组大小足够

   #define MAX_SIZE 100005 // 比题目要求稍大

2. 二分查找边界：特别注意left和right的更新条件

   提示：可以用note[mid] < x而非note[mid] <= x来找到第一个大于等于x的位置

3. 初始条件处理：第一个元素需要单独处理，避免数组访问越界

4. 输入输出效率：对于大规模数据，使用scanf比cin更快

6. 算法思维的进阶应用

这种"降维打击"的思维方式可以推广到许多类似问题：

• 会议室安排问题：计算最少需要多少会议室
• CPU任务调度：确定最少需要的核心数
• 仓库货架管理：优化货物存放策略

其核心模式是：当问题只要求统计某个极值，而非完整过程时，考虑能否找到更本质的数学关系。

7. 不同语言实现的注意事项

虽然我们以C语言为例，但这种思路在其他语言中同样适用：

C++实现要点：

vector<int> note; for(auto x : trains) { auto it = upper_bound(note.begin(), note.end(), x); if(it == note.end()) note.push_back(x); else *it = x; } cout << note.size();

Python实现要点：

import bisect note = [] for x in trains: idx = bisect.bisect_right(note, x) if idx == len(note): note.append(x) else: note[idx] = x print(len(note))

各语言的标准库都提供了二分查找工具，可以简化实现。

8. 测试用例设计与验证

为确保代码正确性，应当设计多种测试场景：

1. 升序序列：[1,2,3,4,5]→ 应输出1
2. 降序序列：[5,4,3,2,1]→ 应输出5
3. 随机序列：[3,1,4,2,5]→ 应输出2
4. 边界情况：空输入、单元素输入、极大值输入

在PTA上提交前，建议先用这些案例本地测试。

9. 性能优化实战技巧

当处理最大规模数据时，还可以考虑以下优化：

1. 输入输出加速：

   setvbuf(stdin, NULL, _IOFBF, 1<<20); setvbuf(stdout, NULL, _IOFBF, 1<<20);

2. 避免不必要的变量：直接在循环中处理输入，不存储全部列车编号

3. 寄存器变量：对频繁访问的变量使用register关键字

4. 循环展开：对于确定的小循环，可以手动展开

这些优化在OJ平台的极端测试用例中可能带来关键的几十毫秒提升。

10. 从具体问题到通用算法

这个列车调度问题实际上是Dilworth定理的一个应用实例：任何有限偏序集的最少链划分等于其最长反链的长度。在这个问题中：

• 链：一条轨道上的递增列车序列
• 反链：不能放在同一轨道上的列车集合
• 最少轨道数 = 最长下降子序列长度

理解这层数学背景，可以帮助我们更好地把握问题本质，在面对变种题目时也能游刃有余。