6-2 铁轨

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

       C 

思路：关键使用一个栈即可,按照顺序弹出，如果可以，应该最后栈为空

输入:
5
1 2 3 4 5
5
5 4 1 2 3
6
6 5 4 3 2 1
输出:
Yes
No

Yes

*/

#include<cstdio>
#include<stack>
using namespace std;

const int maxn = 1005;
int a[maxn];
int n ;
int main(){
    int sign;
    int count; 
    stack<int>s;
    while(scanf("%d", &n) == 1 && n){
        a[1] = 1;
        while(a[1] != 0){
            count = 1;
            for(int i = 1; i <= n ; i++){
                scanf("%d", &a[i]);
                if(a[1] == 0) {
                printf("\n");
                count = 0;
                break;}
            }
        if(count == 0)
            continue;
            int A = 1,B = 1;
            int OK = 1;
            while(B <= n){
                if(A == a[B]){
                    A++; B++;
                }
                else if(!s.empty()&&s.top() == a[B]){
                    s.pop();B++;
                }else if(A <= n) s.push(A++);
                else{
                    OK = 0; break;
                }
            }
            if(OK) printf("OK\n");
            else printf("No\n"); 
        }
    }
    return 0;
}

图片发自简书App