SP95 题解

Dynamic_Arctic_Ice · 2022-09-10 18:33:16 · 题解

题意：这道题的原题意非常啰嗦，但简化后就一句话：一个栈，长度是 n，问能不能让这个栈以 1,2,3, \dots,n 的顺序出栈。

分析： 这题是一道大水题

既然是先进后出，那么我们用栈直接模拟就行了。首先，我们要定义一个栈，叫做 s，然后我们就要开始遍历这个栈了。首先我们定义一个变量 sum，表示你正在模拟的数，然后如果每次栈顶都等于 sum 的话，就出栈，且自增 sum，当什么时候 sum 跟栈的长度 n 一样了，我们这道题就可以结束了。最后，如果在模拟的时候没有输出，最后输出一个 yes 即可。

代码实现：（含注释方便理解）

#include <bits/stdc++.h>
using namespace std;
int n, sum=1, a, x;
bool f=false;
stack<int> s;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x,s.push(x);
    //输入 
    cin>>a;
    while(!s.empty()){
        //只要不空就继续 
        if(s.top()==sum)s.pop(),sum++;
        else if(sum==n)puts("yes"),f=true;
        else puts("yes"),f=true;
        //无论输出什么都标记一下 
    }
    if(!f)puts("yes"); 
    return 0;
}