Codeforces Round #420 (Div. 2) C. Okabe and Boxes(O(n)做法)

题目链接；Codeforces Round #420 (Div. 2) C. Okabe and Boxes

题意：

给你一些操作，add 一个数，remove一个数，这些操作都是在栈上进行。

现在让你将所有remove的数要按照1到n的顺序。

问你至少要重新排序几次。

题解：

其实一个优先队列+一个vector就可以过了的，这里贴一个O(n)的做法。

首先开一个数组当作栈S使用，将add的数放进栈里。

如果满足要要取得话，就正常按着栈S的顺序操作。

如果不满足要求，此时就必须从新排序，然后我们就将栈S清空。

记录一下当前应该输出什么，top就是什么。如果栈S还有元素，那么top就为栈顶。

然后就可以O(n)过去了。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

const int N=3e5+7;
int n,ans,S[N];
int main(){
    scanf("%d",&n);
    char op[10];
    int x,top=0,size=0,now=1;
    while(~scanf("%s",op))
    {
        if(op[0]=='a')
        {
            scanf("%d",&x);
            top=x,S[++size]=x;
        }
        else
        {
            if(top!=now)ans++,size=0,top=++now;
            else
            {
                if(size)size--;
                if(size)top=S[size],++now;
                else top=++now;
            }
        }
    }
    printf("%d
",ans);
    return 0;
}