《算法竞赛入门经典》(第二版) 第 6 章例题 6-2。

题意

这一题的题面较短，其中英文原题也比较容易理解，所以，我们直接分析题意和代码。

本题的题意是右边有一列火车向左开，一列火车可以有很多个车厢，单个车厢来到岔路口的时候，可以选择直接进入 B 轨道，也可以选择在 Station 里面暂存一下，但是 Station 相当于是一个 stack，所以，遵循后进先出的规则。

题目的要求就是，在这样的规则之下，判断给定的序列是否是合法的。

具体我们看几个输入和输出的样例即可。

代码

需要说明一点是，书上给出的代码是有误的，实际提交到 OJ 无法通过。我这里讲解的是我修改之后 AC 的代码。

 1// UVa514 Rails
 2#include <cstdio>
 3#include <stack>
 4#include <string>
 5
 6using namespace std;
 7const int MAXN = 1000 + 10;
 8
 9int n, target[MAXN];
10
11int main() {
12    // 重定向输入数据，省去我们手动输入的繁琐
13    string relativePathToCurrentCFile = "./data/UVa514/input2.txt";
14    // relativePathToCurrentCFile = "./data/UVa210/input3.txt";
15    freopen(string("./ch06" + relativePathToCurrentCFile.substr(1, relativePathToCurrentCFile.size() - 1)).c_str(), "r", stdin);
16
17    while (scanf("%d", &n) == 1) { // 读取 N
18        if (n == 0) {
19            break;
20        }
21        while (true) {
22            scanf("%d", &target[1]); // 读取序列的第一个数
23            if (target[1] == 0) {    // 如果是 0，那么，说明当前这个样例结束了
24                printf("\n");
25                break;
26            }
27            for (int i = 2; i <= n; i++) // 继续读入
28                scanf("%d", &target[i]);
29
30            stack<int> s; // 利用 stack 来进行模拟处理
31            int A = 1, B = 1;
32            int ok = 1;
33            while (B <= n) {
34                if (A == target[B]) { // 当前的车厢和 target 在 B 这个位置所要求的车厢是相同的，那么不用经过 station 直接进入左边的轨道即可
35                    A++;
36                    B++;
37                } else if (!s.empty() && s.top() == target[B]) { // 栈的顶部符合条件
38                    s.pop();
39                    B++;
40                } else if (A <= n) // 目前没有符号条件的，就入栈
41                    s.push(A++);
42                else { // 越界了都没有找到
43                    ok = 0;
44                    break;
45                }
46            }
47            printf("%s\n", ok ? "Yes" : "No");
48        }
49    }
50
51    return 0;
52}