本地测试无误,WA12345

P4387 【深基15.习9】验证栈序列

caramel_qwq @ 2022-03-31 19:22:30

主要是模拟弹出时是否与输入弹出序列有矛盾,有矛盾就是no,否则yes

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int MAXN=1e5+8;
int q,n,ru[MAXN];
int chus[MAXN],chu[MAXN],len;
int main(){
    scanf("%d",&q);
    while(q--){
        memset(chus,0,sizeof(chus));
        len=1;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&ru[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&chu[i]);
        }
        int j=1;
        stack<int> s;
        for(int i=1;i<=n;i++){
            if(s.size()>=1&&s.top()==chu[j]){
                chus[len++]=s.top();
                s.pop();
                j++;
            }
            s.push(ru[i]);
        }
        bool flag=true;
        len--;
        for(int i=1;i<=len;i++){
            if(chus[i]==chu[i]){
                flag=false;
                break;
            }
        }
        if(flag==true){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}

|