画船听雨 @ 2022-01-13 19:55:21
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
int main() {
int q, n, i, j,temp,temp1,temp2,temp3,sum,con,max=0,flag=0,acc=0;
stack<int> a,c;
queue<int> b;
cin >> q;
for (i = 0; i < q; i++) {
cin >> n;
sum = 0;
for (j = 0; j < n; j++) {
cin >> temp;
a.push(temp);
if (temp > max)
max = temp;
}
for (j = 0; j < n; j++) {
cin >> temp1;
b.push(temp1);
}
con = b.size();
while (!b.empty()) {
temp2 = b.front();
temp3 = a.top();
if (temp2 == max) {//如果出现最大值了,就说明出栈序列之后都不能存在逆序输出的。比如1 2 3 4 5和1 2 5 3 4。5出现之后记录下来,然后它后面的3和5隔了一个4,这样就不可行了。
flag = 1;
}
if (temp2 != temp3) {
c.push(a.top());
a.pop();
if (flag == 1) {
acc++;
if (c.size() > 0) {
cout << "No" << endl;
while (!a.empty()) {
a.pop();
}
while (!b.empty()) {
b.pop();
}
while (!c.empty()) {
c.pop();
}
break;
}
}
}
else {
b.pop();
a.pop();
while (!c.empty()) {/*把c
中所有的元素放到a里面*/
a.push(c.top());
c.pop();
}
}
//sum++;
//if (sum >= (con+1)*n/2) {
// cout << "No" << endl;
// break;
//}
if (b.size() == 0)
cout << "Yes" << endl;
}
}
return 0;
}
by Dream_weavers @ 2022-01-13 19:59:37
没有那么麻烦吧,一个栈就够了
#include<bits/stdc++.h>
using namespace std;
stack<int>q;
int n,a[1000001],b[1000001],i,t;
int main()
{
cin>>t;
while(t--)
{
int tmp=1;
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=n;i++)cin>>b[i];
for(i=1;i<=n;i++)
{
q.push(a[i]);
while((q.top())==b[tmp])
{
q.pop(),tmp++;
if(q.empty())break;
}
}if(q.empty())cout<<"Yes"<<endl;
else cout<<"No"<<endl;
while(!q.empty())q.pop();
}
return 0;
}
by devans @ 2022-01-13 20:02:44
Counter Test:
Input:
2
2
1 2
1 2
3
1 2 3
2 3 1
Answer:
Yes
Yes
Output:
Yes
No
by 画船听雨 @ 2022-01-14 17:14:12
@Dream_weavers 确实进行栈模拟快且方便,但我当时没想到啊啊啊啊啊。第一次在洛谷系统写题,没经验
by 画船听雨 @ 2022-01-14 17:16:56
@siXYZit 我靠,好专业的大佬。可以冒昧问一句您是怎么发现反例的吗
by 画船听雨 @ 2022-01-14 17:45:15
@Dream_weavers 而且我发现我这种方法利用的内存确实要小很多,但是太浪费时间了,直接TLE