UVa 514

Rails

from Chapter 3. Data Structures :: Fundamental Data Structures :: Exercises: Beginner

Problem

一辆有N节车厢的火车，利用一个可以后进先出的车站来调换车厢的顺序。假设车厢按进入的顺序从1~N编号，请问是否能够让车厢排列出A1,A2...An这样的顺序。

（1≤N≤1000）

Solution

栈的经典问题。出栈序列有个定理，就是其中任意三个元素Ai,Aj,Ak，都不会出现i<j<k且Aj<Ak<Ai的情况，如果任意三个元素都没有出现这种情况，则可以是一个出栈序列。但是如果根据该定理去枚举三个元素，则时间复杂度为O(N^3)，必然超时，所以这道题跟该定理一点关系都没有。

正确的做法是去模拟火车调换车厢的过程。显然，后进先出的车站明显是一个stack，我们只要利用这个stack，看是否能输出和A序列一样的序列即可。因此，我们按顺序枚举每一个Ai，如果我们当前进入的车厢号还没有到Ai时，则必然得让Ai前面的车厢先放到stack中，然后让编号等于Ai的车厢输出；如果该车厢在stack中，且是栈顶元素，则可以让该车厢出栈；而如果此时发现该车厢在栈中，却又不是栈顶元素，则可以判断想要输出Ai序列是不可能的。因为调换车厢的方案唯一，没有其他选择的余地，所以去模拟它必然是正确的。

该算法的时间复杂度为O(N)。