企业官网建设流程全解析

列车调度这道题，在清华版《数据结构》课程的“栈”这一章里几乎是必刷的经典，放到在线评测平台上又常常变身成一道满分为100的编程题。我第一次拿到AC 100分的时候，其实花了大半个晚上，不是代码写不出来，而是没想明白一个关键点：题目里那个看起来要维护一长串轨道的问题，怎么到最后就等价于在一个数组上做二分替换。后来把教材里的栈调度例题和OJ上的列车调度放到一起对比，才发现自己之前是把两道同名但不同考点的题混在了一起。这篇文章就把这两条线一起捋清楚，既讲怎么判断一个出栈序列是否合法，也讲怎样用O(N log N)的贪心加二分拿到满分，适合正在学数据结构、写实验报告，或者备战面试刷题的朋友。

1. 先说清楚：OJ里的“列车调度”和教材上的“列车调度”是两道题

1.1 教材版列车调度：栈与车厢编组的经典舞步

严蔚敏版《数据结构》第三章讲栈的时候，经常拿火车站的调度站举例。小站只有一条引入线、一条引出线，中间有一段死胡同式的调度线，列车只能从一端进、一端出，这本质上就是一个标准栈。1到n节车厢按编号顺序驶入，经过这个调度站之后，能形成哪些出站顺序？给定一个出站序列，怎样判断它合不合法？

这个问题的核心是判断一个序列能否作为1..n经过单个栈之后的合法输出序列。注意这里的调度站只有一个栈，不是后面OJ题里的“多条平行轨道”。判断方法用的是模拟：遍历目标出站序列里的每一个数x，先把当前还没入栈的、编号不大于x的车厢依次压栈，再尝试弹出栈顶的x。如果栈顶不是x，并且已经没有更多车厢可以压入，那么这个序列就不合法。

举几个具体例子。n=4时，目标序列4 3 2 1是合法的：1、2、3、4依次入栈，4出栈、3出栈、2出栈、1出栈。目标序列4 1 3 2呢？4可以正常出栈，但下一步要弹出1时，栈顶是3，同时所有车厢都已经入过栈了，于是判定非法。很多初学栈的同学会在这里卡住，本质原因是只盯着“下一个目标编号”和“栈顶元素”，却没有意识到已经弹出的车厢无法再回到栈里。这类题多做几道之后，你会慢慢形成直觉：只要某个较大的数先出了栈，后面夹在它和栈顶之间的所有数都已经失去了出栈机会。

1.2 OJ版列车调度：最少轨道数与序列划分

到了在线评测平台上，“列车调度”就换了一副完全不同的面孔。常见的题目描述大致是：入口轨道上的列车按编号1到N依次驶来，出口要求按给定的顺序驶出；调度站里有若干条平行轨道，一辆车进入某条轨道后，这条轨道上的列车必须保持某种单调顺序。问题问的是：至少需要多少条平行轨道，才能完成给定的出站顺序。

这个版本里没有“判断单栈出栈序列合法”的问题，而是变成了“怎样把出站序列划分成最少的若干条单调子序列”。教材版考栈的性质，OJ版考的是单调性维护和贪心替换，两者同名但完全不是一类题。如果你在评测平台上做题，拿到题第一步一定是分辨自己面对的是哪个版本，套错模型的话代码再漂亮也过不了。

我第一次刷到OJ版列车调度时，下意识去写“入栈出栈模拟”，结果样例跑不过，后来才反应过来题目里那个“轨道”不是栈，而是可以把任意车厢放进去的“链”，限制只发生在同一条轨道内部。想通这一点，题目才真正开始可解。

2. 最小轨道数为什么等于最长递增子序列长度

2.1 从模拟轨道分配看贪心策略

我们假设题目规定同一条轨道上的列车编号从入口到出口方向必须递减，也就是说，一辆新车厢想要停到某条轨道尾部，它的编号必须小于这条轨道当前的队尾编号。现在来了编号为x的车，它应该进哪条轨道？

先考虑最简单的情况：遍历所有轨道，找一条“队尾编号大于x”的轨道放进去；如果找不到，就新开一条。这个做法方向是对的，但会留下一个选择问题：能放的轨道有多条时，选哪一条更好？

一种局部最优的策略是：在所有队尾编号大于x的轨道中，选择队尾编号最小的那条。为什么？因为新进入的x会让这条轨道的队尾从原来的较大值变成较小的x，也就是把整条轨道的“可接纳门槛”给降低了；但为了保持后续判断的简单，实际代码里不直接维护轨道编号集合，而是维护一个队尾数组，后面会看到这样做的好处。如果选一条队尾比x大很多的轨道去替换，等于白白浪费了那些“队尾刚好能压住x”的资源，后续来一个中等大小的车厢时可能会被迫新开轨道。

严格证明贪心正确性需要一点偏序集的功夫，但直觉上可以这样想：队尾数组越“小”、越紧凑，未来能接纳新车的轨道就越多。每一次替换都是把某个位置“挖深一点”，没有破坏任何已经形成的约束关系，所以这种局部调整不会让全局变差。

2.2 tails数组的单调性与替换操作

用代码实现时，我们维护一个数组tails，它从前往后严格递增。tails[i]的含义可以理解为：使用当前已经出现过的车厢，在保证最优划分的情况下，长度为i+1的某条链的“最小可能末尾值”。不用被这句话吓住，实际操作非常机械：

• 每读到一辆车的编号x，在tails里找第一个大于x的位置p；
• 找到了，就把tails[p]替换成x；
• 找不到（x比tails里所有数字都大），就push_back(x)。

这个过程等价于计算一个序列的最长递增子序列长度，最终tails.size()就是答案。下面用一个PTA上常见的样例来走一遍。输入是9辆车，出站顺序为：

8 4 2 5 3 9 1 6 7

tails数组每一步的变化：

最终tails长度为4，答案就是4。注意看每一步：只要做的是替换，数组长度就不变；只有当x比所有尾巴都大时长度才增加。这也是LIS问题的标准特征。

2.3 Dilworth定理视角：为什么下界恰好等于上界

如果你接触过组合数学，会发现这里有个很漂亮的结论：最少递减子序列划分数等于最长递增子序列长度，这就是Dilworth定理在序列上的直接体现。把它翻译成人话就是两句话：

第一，如果原序列中存在一段严格递增的元素a1 < a2 < ... < ak，那么它们不可能放在同一条递减轨道里，所以轨道数至少是k。也就是说，LIS长度给出了答案的下界。

第二，贪心替换算法总能用不超过LIS长度的条数把所有车厢都放完，这说明LIS长度也就是上界。下界与上界一碰，答案就等于LIS长度。

所以这个题根本不关心你给每个车厢具体分配哪条轨道，只要算LIS长度即可。这也是为什么网上几乎所有AC代码都只维护一个tails数组，因为真实轨道里的车厢列表完全不需要存下来。

3. 满分代码的进化：暴力模拟、贪心替换到二分维护

3.1 三种方案的复杂度对比

我在实际写题时先试过比较暴力的做法，然后才优化到二分，过程如下：

方案A不是没有价值，它非常适合在小数据下验证贪心策略。等你确认暴力模拟结果和贪心结果一致，再换成方案C提交，基本一次AC。这也是做对拍的标准流程，后面会细说。

3.2 含注释的满分C++实现

下面的代码是我最终提交的满分版本，代码很短，但每一行都值得解释。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, x; cin >> n; vector<int> tails; // 严格递增，长度就是当前最优轨道数 while (n--) { cin >> x; // 找第一个大于等于 x 的位置 vector<int>::iterator it = lower_bound(tails.begin(), tails.end(), x); if (it == tails.end()) { // 所有队尾都比 x 小，说明当前轨道都放不下，新开一条 tails.push_back(x); } else { // 用 x 替换该位置的队尾值，相当于把某条轨道“压得更低” *it = x; } } cout << tails.size() << '\n'; return 0; }

这里用lower_bound找的是“第一个大于等于x”的位置。由于题目里1到N的排列不出现重复编号，它和“第一个大于x”是等价的。如果你在变体题中允许相同编号且同一条轨道也允许相等，就把lower_bound换成upper_bound，语义变成“第一个大于x”，然后替换。两行之差，边界行为完全不同，后面第4章再展开。

3.3 验证样例与边界测试

把上面提到的那组数据喂进去，程序输出4，和预期一致。

自己动手补几个边界用例：

• 输入是严格递增序列1 2 3 ... N，每来一辆车都比前面所有尾巴大，于是每次都会push_back，答案N，正确。
• 输入是严格递减序列N ... 3 2 1，每来一辆车都找到第一个比它大的位置并替换，tails永远只有一个元素，答案1，正确。
• 输入只有一辆车，输出1，正确。

这几个极端情况基本能覆盖提交前最粗心的错误。AC之后我习惯再跑一组手搓的随机数据，和暴力模拟对拍一下，求个心安。

4. 从100分提交里提炼的易错点和查错套路

4.1 lower_bound还是upper_bound：边界条件的抉择

这个点看起来小，实际翻车率特别高。标准题意下编号是1到N的排列，没有重复，用lower_bound和upper_bound结果完全一样；一旦题目变形为“编号可以重复”，就必须仔细读题：

• 题干写“同一条轨道上的列车编号必须严格递减”，那就用lower_bound，等于不允许出现相等的车停在同一轨道；
• 题干写“同一条轨道上后进来的车编号不大于之前的车”，说明允许相等，要用upper_bound，把第一个严格大于当前车的位置替换掉。

很多网上代码默认用lower_bound，如果你换题目时没改这里，轻则边界多算一条，重则直接WA。我的习惯是一律根据“是否允许相等”来写成lower_bound或upper_bound，而不是照抄模板。

4.2 大数据量下的输入输出与内存细节

N到10^5时，cin/cout不关同步也勉强能过；N到10^6时差别就很明显了。建议开头直接加两行：

ios::sync_with_stdio(false); cin.tie(nullptr);

或者直接用scanf和printf。另外内存上直接开vector 就够了，不需要搞手写数组或者链表。千万别图方便用set或multiset来维护tails，不是不能用，而是set的迭代器替换操作比vector的二分下标替换慢不少，在极限数据下容易超时。

还有一个容易被忽略的点：如果题目是多组输入，每次循环开始前必须把tails清空。否则上一组数据留下的尾巴会对下一组造成干扰，出现莫名其妙的输出偏大。我帮同学debug时见过几次这种情况，都不是算法错，纯粹是global变量没重置。

4.3 如何构造对拍数据自测

提交之前想验证自己的二分实现和“真实分配轨道”的模拟结果是否一致，最有效的方法是写一个慢速正确的程序去对拍。慢速版可以这样写：

vector<vector<int>> tracks; for each x: 找到第一条满足 tracks[i].back() > x 的轨道 如果找到，把 x 放到这条轨道尾部；否则新开一条轨道

注意慢速版一定要“完全模拟真实过程”，不要掺杂任何LIS优化，这样才能作为正确性基准。然后用随机数据生成器造输入，脚本不停跑对比：

for i in $(seq 1 1000); do python3 make.py > in.txt ./fast < in.txt > out1.txt ./slow < in.txt > out2.txt if ! diff -q out1.txt out2.txt > /dev/null; then echo "WA on test $i" break fi done

make.py里生成一个1到N的随机排列，N可以取50到200，既足够暴露出错误，又不会让慢速版跑太久。一旦两边结果不一致，立刻打印这组输入，手动画轨道路径找原因。这个流程我几乎每次写数据结构题都会跑一遍，省下的调试时间远超那几分钟写脚本的成本。

4.4 常见的“思路对但没AC”的隐蔽原因

除了上面说的那几个点，还有几个我实际遇到过的问题：

• 用vector<int>::iterator it = lower_bound(...)时，如果tails为空，lower_bound返回end()，此时判断逻辑千万别写反。
• 输出问题：题目如果要求每组输出后再空一行，注意换行符位置；好在大多数题目只要一个普通'\n'。
• 数组越界：如果有人用传统数组而不是vector，容易把tails容量开小一截，N=10^5的时候随机测试可能碰巧不崩，提交就溢出。建议直接用vector，免掉这个隐患。

5. 回到教材：栈调度合法性判断与卡特兰数

5.1 出栈序列合法性判断的模拟算法

教材版列车调度的代码其实也很短。给定一个出站序列out，判断它能否由1..n依次入栈得到：

bool check(const vector<int>& out, int n) { stack<int> st; int next = 1; // 下一个要入栈的车厢编号 for (int x : out) { // 栈顶不是 x 且还有车没入栈，就继续压入 while (next <= n && (st.empty() || st.top() != x)) { st.push(next++); } if (!st.empty() && st.top() == x) { st.pop(); } else { return false; } } return true; }

这段代码的核心是：每次处理目标x时，先把所有还没入栈且编号不大于x的车厢压进去，然后尝试弹出x。栈顶匹配不上且已经无可入栈车厢，就非法。以n=5为例，3 5 4 2 1合法：先压1、2、3，弹出3；再处理5，压4、5，弹出5；随后4、2、1依次弹出。而3 2 5 1 4非法，因为弹出的顺序里1夹在2和4中间，栈无法满足这个时序。

5.2 所有合法序列计数：卡特兰数

n节车厢经过一个栈，能得到多少种不同的合法出栈序列？答案是卡特兰数：

• C_n = (1 / (n + 1)) * C(2n, n)

n=3时合法序列一共有5个：123、132、213、231、321。你可以把“入栈”看成左括号，“出栈”看成右括号，任意前缀都不能让出栈次数超过入栈次数，这就成了经典的括号匹配计数。实际计算时可以用递推：

long long catalan[35]; catalan[0] = 1; for (int i = 1; i <= 30; i++) { catalan[i] = catalan[i - 1] * (4 * i - 2) / (i + 1); }

注意n超过30左右数值就很大了，面试或实验里通常只要求算到30以内；再大就要用高精度或者Python的整数。这道题还经常和“二叉树形态计数”“凸多边形三角划分”绑定在一起考，它们共享同一套卡特兰数公式，记一个等于记一串。

5.3 这类题在面试中的打开方式

面试里遇到“列车调度”相关题，最怕的不是写不出来，而是只会背代码，说不清为什么。建议把三个模型串起来记忆：出栈序列合法性判断等于栈模拟；最少轨道数等于LIS的贪心二分；合法序列计数等于卡特兰数。面试官如果追问，你就从“单栈限制”讲到“多轨道链划分”，再点一句Dilworth定理，基本上就能从“背题选手”升级成“理解原理的候选人”。如果让我出一道变形题，我可能会把轨道数改成“每辆车的编号可以相同但同一条轨道不允许相等”，然后观察你能不能反应过来把lower_bound改成upper_bound。

另外，把这道题的思维迁移到其他场景也很有用。比如操作系统里进程按优先级排队、数据库里分区表的数据分布、网络里报文按端口分流，“调度”二字的本质都是给一堆有序元素找一个满足约束的容器划分。数据结构课里刷过的每道经典题，都可能在某个角落以另一种身份重新出现。

最后分享一个小技巧：刷这类“顺序序列划分”的题，我会在草稿纸上先把小规模数据的所有分配方案画出来，再去看算法代码。画过一遍之后，tails数组的每一步变化就不再是抽象的替换，而是能看到一条条轨道真实地在变矮变短。列车调度这道题之所以值得反复刷，是因为它同时压中了栈、贪心、二分、组合计数四个数据结构高频核心知识点，一道题顶四道题。那个AC 100分的记录不是终点，以后看到“调度”“排队”“分区”这类关键词时，脑子里能瞬间弹出这条主线，才算真正把分“拿到手”。