首页 > 代码库 > Codeforces 821C Okabe and Boxes

Codeforces 821C Okabe and Boxes

题意:

给定一个n,然后有2n个指令,分别是add x, remove, add x 就是将x加入到栈中, remove 就是从栈顶移除, 然后移除的元素一定要有序, 不然就需要resort(重排)一次, 问最少需要重排多少次。

技术分享

分析:

可以看出,每次只有栈顶元素和应该移除的元素不符合时候才需要重排, 所以重排后可以想象成栈中所有的元素都在他最佳的位置,那么我们就可以忽视掉这些重排后的元素, 把栈清空然后继续执行操作, 这样可以做到O(n)的复杂度。

另外如果栈顶元素正是需要移除的元素, 那么我们就弹出栈顶元素,不需要清空。

代码:

#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
    vector<int> sta;
    scanf("%d", &n);
    int ans = 0;
    int trash = 1;
    int Top = 0;
    for(int kase = 0; kase < 2 * n; kase++){
        char choice[20];
        scanf("%s", choice);
        if(choice[0] == a){
            int k;
            scanf("%d", &k);
            sta.push_back(k);
        }
        else{
            if(!sta.empty()){
                if(sta.back() != trash){
                    ans++;
                    sta.clear();
                }
                else sta.pop_back();
            }
            trash++;
        }
    }
    printf("%d\n", ans);
}

 

Codeforces 821C Okabe and Boxes