欢迎访问我的Uva题解目录哦 https://blog.****.net/richenyunqi/article/details/81149109

题目描述

题意解析

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

算法设计

这道题实质上是给定入栈次序，判断是否能够产生相应的出栈次序的题目。当出栈元素比栈顶元素小时，则不能产生相应的出栈次序。

C++代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    for(int ii=0;~scanf("%d",&n)&&n!=0;++ii){
        int exit[n];
        while(~scanf("%d",&exit[0])&&exit[0]!=0){
            for(int i=1;i<n;++i)
                scanf("%d",&exit[i]);
            stack<int>s;//栈
            bool yes=true;//标志能否产生相应的出栈次序
            int MAX=0;//出栈的最大元素
            for(int i=0;i<n;++i)//遍历出栈次序
                if(s.empty()||s.top()<exit[i]){//栈空或者当前出栈元素比栈顶元素大
                    for(int j=MAX+1;j<exit[i];++j)//把[最大出栈元素,当前出栈元素)之间的数入栈
                        s.push(j);
                    MAX=max(exit[i],MAX);//更新最大出栈元素
                }else if(s.top()==exit[i]){//栈顶元素和当前出栈元素相同
                    s.pop();//出栈
                    MAX=max(exit[i],MAX);//更新最大出栈元素
                }else{//当前出栈元素比栈顶元素小，则不能产生相应出栈元素
                    yes=false;
                    break;
                }
            puts(yes?"Yes":"No");
        }
        puts("");
    }
    return 0;
}