UVA 514 - Rails

紫书 P140，栈的模板题。
秒切这题的 dalao 请跳过本文
这是写给像我一样菜的蒟蒻的

题面 提交

题目

题意

已知入栈序列 $1,2,3,4,...n$，问能否得到出栈序列$Target_1,Target_2,Target_3,...Target_n$（要求每个元素只进栈一次）

输入格式

单个输入文件中包含若干组数据。
每组数据第一行给出$n$
之后若干行，每行表示一个询问，每行$n$个数，第$i$个数表示$Targe{t}_i$，保证为 $1,2,...,n$ 的一个排列
$Targe{t}_1=0$表示该组输入结束
$n=0$表示输入结束

输出格式

对于每个询问，输出 Yes 或 No
每两组数据间应有一空行

解答

分析

令$A$表示下一个进栈元素，$Targe{t}_B$表示下一个期望元素

初始化，A=B=1，栈 s 为空

对于每一个 A，分类讨论：

1.$A=Targe{t}_B$，显然 A 进栈后立即出栈，A++，B++
2.栈非空且$s.top()=Targe{t}_B$，即栈顶元素为下一个期望元素，s.pop() 出栈，B++
3.$A<=n$，说明还有输入，但期望的元素并不是它或栈顶元素，那只能入栈（没有其他方案）
4.以上情况均不满足，说明输入已经全部入栈，栈中有元素但并不是期望元素，一定无解

AC 代码

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

const int MAXN=1005;

int n,target[MAXN];

void solve();

int main(){
    while((cin >> n)&&(n)){
        while((cin >> target[1])&&(target[1])){
            for(int i=2;i<=n;i++) cin >> target[i];
            solve();
        }
        putchar('\n');
    }
    return 0;
}

void solve(){
    stack<int> s;
    int A=1,B=1;
    while(B<=n){
        if(A==target[B]) {
            ++A;
            ++B;
        }
        else if((!s.empty())&&(s.top()==target[B])){
            s.pop();
            ++B;
        }
        else if(A<=n) s.push(A++);
        else {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
    return;
}
​