SP95 题解

sto_yyrdxh_orz · 2022-08-21 14:13:22 · 题解

题目大意：

第一行输入一个数字 n，第二行输入 n 个数字，第三行一个正整数 0，表示输入结束，如果能够按照 最后进入小街的爱情车一定要先离开小街 将题目输入的 n 个数从小到大排好序就输出 yes ,否则输出 no。

观点：

感觉这道题中的数字 0 意义不大，因为题目都给出了数字数量的个数 n，以没必要再输入 0。

题目分析：

通过题目中的一句话 最后进入小街的爱情车一定要先离开小街 我们可以联想到栈，因为栈的性质就是先进后出，后进先出，所以这道题就被我们简化成了能否用栈对输入的 n 个数字按照升序排序。

思路：

我们用一个变量 sum 来存储按照升序规则的下一个元素，每次进行比较，如果当前栈的顶部元素和 sum 相等，就将顶部元素出战，并将 sum 加 1，最后如果栈不为空就输出 no 否则输出 yes。

具体代码：

#include <iostream>
#include <stack>
//栈需要用到的头文件
using namespace std;
int n, sum;
stack<int> s;
int a;
//栈的定义方法
int main(){
    cin>>n;
    sum=1;
    //与栈内元素比较用的变量 
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        s.push(x);
        //往栈里插入元素 
        if(!s.empty()){
            //如果不为空 
            if(s.top()==sum){
                s.pop();
                sum++;
                //按照升序规则的下一个元素 
            }
        }
        else{
            //栈已经空了说明可以按照升序排序 
            cout<<"yes";
            return 0;
            //输出完就可以结束了 
        }
        //第一轮出栈操作并不能保证能出栈的全部出栈，所以在下面还要进行一次操作 
    }
    cin>>a;
    //没用，不过还是输入一下吧 
    while(!s.empty()){
        //第二轮操作 
        if(s.top()==sum){
            s.pop();
            sum++;
            //按照升序规则的下一个元素 
        }
        else if(sum==n){
            //如果sum加到了n，说明元素全部出栈 
            cout<<"yes";
            return 0;
        } 
        else{
            //说明无论如何都完成不了了 
            cout<<"no";
            return 0;
        }
    }
    cout<<"yes"; 
    return 0;
}