CF Okabe and Boxes
题目描述
给你一个n; 以栈的方式乱序存入n个数 其中有两个操作
add x 压入一个x元素；
remove 出栈
保证 会压入n 个元素并且会将n个元素弹出 现在需要你按小到大的元素弹出来 当发现不满足条件时你能改变栈的顺序 问你最少需要排多少次才能从小到大弹出；
1 ≤ n ≤ 3·10^5
分析：问题要我们回答次数 所以并不用真正去排它（并且也会超时） 所以只需要记录前多少我排了，当到这里时直接出栈就好；
#include<bits/stdc++.h>
using namespace std;
int main(){
// FILE *fp;
// fp=fopen("1.txt","r");
int n;
char s[10];
int x,ans=0,index=1;
scanf("%d",&n);
int sta[300005];
int top=1,i=1;
n*=2;
while(n--){
scanf("%s",s);
if(s[0]=='a') {scanf("%d",&x);sta[top++]=x;}
else {
if(sta[top-1]==i||top<=index);
else {
ans++;
index=top;
}
if(top<=index) index--;
top--,i++;
// for(int i=1;i<top;i++)
// cout<<sta[i]<<endl;
}
// cout<<top<<' '<<index<<endl;
}
cout<<ans<<endl;
}
也可以用栈写 遇到不满足条件的就全部清空，当下次遇到空时表示这里满足条件
查看11道真题和解析
投递快手等公司10个岗位
