9912请你编程

电脑报编辑部 1999年12月刊 请你编程

题目

　　在PopPush这个城市里，有一个非常著名的火车站。由于修建年代久远，这个车站只有一根轨道。而且，该车站又是终点站，所以火车进入和离开车站都依靠这个轨道，且只能从一端进出。该城市正是因此而得名。

　　但这样一来，出现了一个很奇特的现象：如果有1、2、3这三列火车将先后进入车站，则火车出站的各种排列中不可能出现3、1、2。因为如果3是第一个进站的火车，说明1和2都已进站了。而2比1晚进车站，所以如果2还未出站的话，1不可能出站。但是，出站的各种排列中有可能出现1、2、3，即1进站后在2进站之前就已出站，2在3进站之前也出了站。

　　程序要求如下：

1. 输入数据从文本文件rails.txt中读取。输入数据文件格式为：输入数据中又包含若干组；每一组的第一行为一个整数N，表示有N辆火车，N<=1000。以下每一行表示火车出站的排列顺序，用0来表示这组的结束；若N=0，则表示输入结束。
2. 若这种排列可能出现，则输出Yes，反之，输出No；每一组数据要空一行。

　　注：排列序列中的1、2、3、4...表示在这些火车进站之前，它们的先后顺序。

　　输入数据范例：

5

1 2 3 4 5

5 4 1 2 3

0

6

6 5 4 3 2 1

0

0

　　输出数据范例：

Yes

No

　　本期题目由上海的卜天明提供。

　　来稿请寄磁盘稿或用E－mail（[email protected]）投稿，请写明解题思路和源程序（包含详细的注解），寄到电脑报编辑部的收信地址或E－mail信箱。来稿截止日期：2000年1月15日。

解答

思路

代码是由 New Bing 给出：

这是一道经典的数据结构算法问题，叫做铁轨问题。

使用了两个栈，一个栈用于存储进站的火车编号，另一个栈用于模拟出站的火车编号。在模拟过程中，如果当前进站的火车编号与出站的火车编号相同，则将该火车出站；否则，将该火车进站。最后，如果所有火车都已经出站，则说明这种排列可能出现；否则，说明这种排列不可能出现。

P.S. 其实也可以使用一个栈(如图例)，将入栈序列编号，这样问题就转换成 1,2,3... 入站，出站序列是否能出现的问题。

Code

C

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000

int main()
{
    int n, i, j, k;
    int a[MAX], b[MAX], s[MAX];
    while (scanf("%d", &n) == 1 && n)
    {
        while (scanf("%d", &a[1]) == 1 && a[1])
        {
            for (i = 2; i <= n; i++)
                scanf("%d", &a[i]);
            for (i = 1, j = 1, k = 0; i <= n; i++)
            {
                b[++k] = i;
                while (j <= n && b[k] == a[j])
                    j++, k--;
            }
            printf("%s\n", k ? "No" : "Yes");
        }
        printf("\n");
    }
    return 0;
}

Python

while True:
    n = int(input())
    if n == 0:
        break
    while True:
        a = list(map(int, input().split()))
        if a[0] == 0:
            break
        b = []
        c = []
        for i in range(1, n + 1):
            b.append(i)
        j = 1
        for i in range(1, n + 1):
            c.append(b[i - 1])
            while len(c) > 0 and c[-1] == a[j]:
                c.pop()
                j += 1
        if len(c) == 0:
            print("Yes")
        else:
            print("No")
    print()