查看“9912请你编程”的源代码

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

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

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

　　程序要求如下：
# 输入数据从文本文件rails.txt中读取。输入数据文件格式为：输入数据中又包含若干组；每一组的第一行为一个整数N，表示有N辆火车，N<=1000。以下每一行表示火车出站的排列顺序，用0来表示这组的结束；若N=0，则表示输入结束。
# 若这种排列可能出现，则输出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（software@cpcw.com）投稿，请写明解题思路和源程序（包含详细的注解），寄到电脑报编辑部的收信地址或E－mail信箱。来稿截止日期：2000年1月15日。

=== 解答 ===

==== 思路 ====
[[文件:9912qa.jpg|无框]]

代码是由 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()

[[分类:Develop]]
[[分类:Problem-Solving]]