自动搬运

查看原文

来自洛谷，原作者为

	Clear_yu 没有黎明的黑暗，我也愿在其间穿行，去追寻我的那束光

搬运于2025-08-24 21:59:37，当前版本为作者最后更新于2020-01-07 10:55:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻的第二篇题解~STL大法好

在红题里找黄题做

通过简单地阅读题目可知，对于给定的入栈序列 poshed话说为什么不是pushed，错字受，验证序列poped是否为入栈序列可能的一个出栈序列。

由于数据范围比较小(n≤100000)不会爆栈，那为什么不用STL来模拟呢（STL大法好！破音~）

下面是最爱的代码

#include<iostream>
#include<stack>
using namespace std;
stack<int>q;//栈q 
int p,n;//p组数据，n为序列长度 
int main()
{
	cin>>p;
	while(p--)
	{
		cin>>n;
		int a[n+1],b[n+1],sum=1;//入栈队列a，待检验队列b，计数器sum 
		for(int i=1;i<=n;i++)
		cin>>a[i];
		for(int i=1;i<=n;i++)
		cin>>b[i];//平平无奇的输入 
		for(int i=1;i<=n;i++)
		{
			q.push(a[i]);//入栈 
			while((q.top())==b[sum])//当栈顶元素与b中当前元素相同时出栈 
			{
				q.pop(),sum++;//sum++到b下一个元素 
				if(q.empty())break;//注意这里，第一次RE就因为当栈空时还用了出栈操作，所以要手动结束循环 
			}
		}
		if(q.empty()) cout<<"Yes"<<endl;//如果栈为空说明出栈序列b正确 
		else cout<<"No"<<endl;
		while(!q.empty())q.pop();//清空栈 
	}
	return 0;//谢幕 
}

喜欢就点个赞吧！