ACM模版

描述

题解

这个是模拟栈的操作，不过有稍微不同的是，题目希望按顺序 pop() 1∼n ， 如果出现无法按顺序，那么就可以对栈内元素进行一个排序，所以呢，最后结果是求最少需要排序的次数。

这里有一个很强的条件，就是不会出现不合法的情况，也就是说，当我们该输出 x 时，栈内一定会有 x，所以呢，原本我们需要暴力解一下，每次遇见不合法就排序，现在可以直接清空，当我们 pop() 时，如果栈内为空，默认此时一定是可以弹出想要的值的，不过我们提前弹出了，所以这里直接 O(n) 可解了。使用 <vector> 向量比较好写一些。

代码

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

char str[7];
vector<int> vi;

int n;

int main()
{
    scanf("%d", &n);

    int cnt = 1, ans = 0, x;
    for (int i = 1; i <= 2 * n; i++)
    {
        scanf("%s", str);
        if (str[0] == 'a')
        {
            scanf("%d", &x);
            vi.push_back(x);
        }
        else
        {
            if (vi.empty()) ;
            else if (vi.back() == cnt)
            {
                vi.pop_back();
            }
            else
            {
                ans++;
                vi.clear();
            }
            cnt++;
        }
    }

    cout << ans << endl;

    return 0;
}