求助

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

XPKAAA @ 2021-08-07 19:25:13

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<stack>
using namespace std;
int n,q,poped[100010],pushed[100010],top,j,sum;
stack<int> a;
bool cnt;
int main()
{
    cin>>q;
    while(q--)
    {
        j=0;
        top=0;
        cnt=true;
        cin>>n;
        for(int i=1; i<=n; i++)
        {
            cin>>pushed[i];
        }
        for(int i=1; i<=n; i++)
        {
            cin>>poped[i];
        }
        a.push(pushed[++j]);
        while(!a.empty())
        {
            top++;
            if(poped[top]>a.top())
            {
                while(poped[top]>a.top())
                {
                    a.push(pushed[++j]);
                }
                a.pop();
            }
            else if(poped[top]==a.top()) 
            {
                sum=a.top();
                a.pop();
                if((j<n)&&(poped[top+1]>sum))
                {
                    a.push(pushed[++j]);
                }
            }
            else if(top>n) 
            {
                cnt=true;
                break;
            }
            else
            {
                cnt=false;
                break;
            }
        }
        if(cnt)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0;
}

|