821C - Okabe and Boxes ——优先队列＋手动模拟栈

野性酷女 2022-06-13 03:52 223阅读 0赞

Think:
1题意：模拟一个栈，有两种操作，栈顶增加一个元素，栈顶移除一个元素，要求元素按照编号大小移除，移除前可以选择是否调整栈内元素顺序，询问最少调整次数
2方法：优先队列＋手动模拟栈
3反思：注意暴力模拟＋排序会超时

codeforces题目链接

以下为Accepted代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 4;
priority_queue <int, vector<int>, greater<int> > q;
int tp, link[N];
int main(){
    int n, i, x, num;
    char st[14];
    scanf("%d", &n);
    getchar();
    tp = 0, num = 0;
    for(i = 1; i <= 2*n; i++){
        scanf("%s", st);
        if(st[0] == 'a'){
            scanf("%d", &x);
            q.push(x);
            link[tp++] = x;
        }
        else if(st[0] == 'r'){
            if(tp){
                int t = q.top();
                if(t == link[tp-1]){
                    tp--;
                    q.pop();
                }
                else {
                    num++;
                    tp = 0;
                    q.pop();
                }
            }
            else {
                q.pop();
            }
        }
    }
    printf("%d\n", num);
    return 0;
}