洛谷 UVA 514 铁轨 Rails

UVA514 铁轨 Rails

Input

The input file consists of blocks of lines. Each block except the last describes one train and possibly
more requirements for its reorganization. In the first line of the block there is the integer N described
above. In each of the next lines of the block there is a permutation of 1, 2, . . . , N. The last line of the
block contains just ‘0’.
The last block consists of just one line containing ‘0’.

Output

The output file contains the lines corresponding to the lines with permutations in the input file. A line
of the output file contains ‘Yes’ if it is possible to marshal the coaches in the order required on the
corresponding line of the input file. Otherwise it contains ‘No’. In addition, there is one empty line after
the lines corresponding to one block of the input file. There is no line in the output file corresponding
to the last “null” block of the input file.

Sample Input

5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0

Sample Output

Yes
No

Yes

题意翻译

某城市有一个火车站，铁轨铺设如图。有n节车厢从A方向驶入车站，按进站的顺序编号为1～n。你的任务是判断是否能让他们按照某种特定的顺序进入B方向的铁轨并驶出车站。例如，出栈顺序（5 4 1 2 3）是不可能的，但（5 4 3 2 1）是可能的。 为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每节车厢，一旦从A移入C，就不能返回A了;一旦从C移入B，就不能返回C了。也就是说，在任意时刻，只有两种选择：A到C和C到B。

对于每一组数据，第一行是一个整数 NN 。接下来若干行数据，每行 NN 个数，代表 11 ~ NN 车厢的出栈顺序，最后一组数据只有一个整数 0 。对于每一组数据，在最后输出空行。

最后一组数据的 N=0 ，不输出。

n<=1000

#include <iostream>
#include <stack>
using namespace std;
int main() {
	int n, m;
	while (cin >> n && n) {
		int num[n + 1];
		while(cin >> num[1] && num[1]) {
			stack<int> s;
			int x = 1;
			for (int i = 2; i <= n; i++) cin >> num[i];
			for (int i = 1; i <= n; i++) {
				s.push(i);
				while (!s.empty() && s.top() == num[x]) {
					x++;
					s.pop();
				}
			}
			if (s.size() == 0) cout << "Yes\n";
			else cout << "No\n";
		}
		cout << endl; 
	}
	return 0;
}