rt

题目描述

给出 pushed 和 poped 两个序列，其取值从 1 到 n(n≤100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。每个测试点有多组数据。

输入格式

第一行输入一个正整数 T，表示数据组数。对于每组数据，第一行输入一个正整数 n；第二行输入 n 个正整数，表示入栈序列；第三行输入 n 个正整数，表示出栈序列。

输出格式

对于每组数据单独输出一行 Yes 或 No。

样例

Input 1

1

5

1 2 3 4 5

4 5 3 2 1

Output 1

Yes

Input 2

1

5

1 2 3 4 5

3 5 2 4 1

Output 2

No

样例解释

对于第一个测试样例，入栈序列为 1 2 3 4 5，出栈序列为 4 5 3 2 1，可以通过以下操作得到出栈序列：先将 1、2、3 依次入栈，然后将 3、2、1 依次出栈，再将 4、5 依次入栈，最后将 5、4 依次出栈，故输出 Yes。

对于第二个测试样例，入栈序列为 1 2 3 4 5，出栈序列为 3 5 2 4 1，无法通过栈的操作得到出栈序列，故输出 No。

数据范围

n≤100000

本蒟蒻代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int pushed[N],poped[N];
int n;
int main(){
  int _;
  cin>>_;
  while(_--){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>pushed[i];
    for(int i=1;i<=n;i++) cin>>poped[i];
    stack<int> stk;
    int p=1;
    bool flag=true;
    for(int i=1;i<=n;i++){
      while(stk.empty()||(skt.top()!=popde[i]&&p<=n)){
        stk.push(pushed[p++]);
      }
      if(stk.empty()&&stk.top()==poped[i]){
        stk.pop();
      }
      else{
        cout<<"No\n";
        flag=false; 
        break;
      }
    }
    if(flag){
      cout<<"Yes\n";
    }
  }
  return 0;
}

谢谢啦~~~