LRJ入门经典（基础篇）——2.铁轨

2.铁轨

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

分析：
1.暴力求解:将进栈顺序为1，2，3，4，5的每一行种可能的出栈顺序求解出来。耗费时间长，很可能不满足时间复杂度的要求
2.逆向思维：我们可以根据出栈顺序（B）来推出进栈顺序（A），思路如下：
将B的元素依次与A的元素和C的栈顶元素相比较：

• 1.若A=B则A→B;
• 2.若B=C则C→B;
• 3.若B!=C&&B!=A&&A!=empty则A→C;
• 4.若B!=C&&B!=A&&A=empty则没有该输出序列

#include<iostream>
#include<stack>
#include<cstdio>
using namespace std;
const int MAXN = 100;

int n;//入站的个数
int A[MAXN], B[MAXN];
stack<int> C;
int a = 0,b = 0;//记录A，B的当前元素
int main(){

    scanf("%d", &n);
    for(int i=0;i<n;i++){//输入入站顺序
            scanf("%d",&A[i]);
        }
    for(int i=0;i<n;i++){//输入出站顺序
            scanf("%d",&B[i]);
        }

    while(a<n){
        if(C.empty()){
            if(B[b] == A[a]){//A=B
                cout<<"A→B"<<endl;
                a++;
                b++;
            }
            if(B[b] != A[a]){
                cout<<"A→C"<<endl;
                C.push(A[a]);
                a++;
            }
        }

        if(!C.empty()){

                if(B[b]==A[a]){//A=B
                    cout<<"A→B"<<endl;
                    a++;
                    b++;
                }



                while(B[b]==C.top()){//B=C
                    cout<<"C→B"<<endl;
                    C.pop();
                    b++;
                    if(C.empty())break;
                }


                if(B[b]!=A[a] && C.top()!=B[b]){//A!=B&&B!=C&&A!=empty
                    cout<<"A→C"<<endl;
                    C.push(A[a]);
                    a++;
                }
        }

    }

    if(C.empty()){
        cout<<"步骤如上"<<endl;
    }else{
        cout<<"没有该输出序列"<<endl;
    }
    return 0;
}

测试数据:

5
1
2
3
4
5
5
4
3
2
1