COJ 0015 20602铁轨

传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=15

20602铁轨

难度级别：B；运行时间限制：1000ms；运行空间限制：51200KB；代码长度限制：2000000B

试题描述

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

现在给你一种1到n的排列，请你判断是否是题目描述的一种可能，如果是请输出yes，否则输出no

输入

两行，第一行有一个正整数n，表示有n节车厢，第二行有n个正整数，即1到n的一种排列，两两之间有一个空格分隔。

输出

yes或者no

输入示例

5
5 4 1 2 3

输出示例

其他说明

对于 100%的数据，0 < n ≤ 100。

栈瞎搞

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<stack>
 6 using namespace std;
 7 int n,A[100+10],top=0;stack<int>S;
 8 inline int read(){
 9     int x=0,sig=1;char ch=getchar();
10     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
11     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
12     return x*=sig;
13 }
14 inline void write(int x){
15     if(x==0){putchar('0');return;} if(x<0) putchar('-'),x=-x;
16     int len=0,buf[15]; while(x) buf[len++]=x%10,x/=10;
17     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
18 }
19 void init(){
20     n=read();
21     for(int i=1;i<=n;i++) A[i]=read();
22     top=1;
23     return;
24 }
25 void work(){
26     int tmp;
27     for(int i=1;i<=n;i++){
28         S.push(i);
29         while(!S.empty()&&S.top()==A[top]){
30             S.pop();top++;
31         }
32     }
33     return;
34 }
35 void print(){
36     if(S.empty()) puts("yes");
37     else puts("no");
38     return;
39 }
40 int main(){
41     init();work();print();return 0;
42 }