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

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

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

[codeforces题目链接][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;
    }

[codeforces]: http://codeforces.com/problemset/problem/821/C

发表评论取消回复

表情：

评论列表（有 0 条评论，105人围观）

还没有评论，来说两句吧...

相关阅读

相关 c++队列及优先队列

队列特点：先进先出，可形成有序的结构，运用于算法设计；常用操作： Cpp: queue<int> q; //定义； q.empty

淩亂°似流年/ 2023年10月21日 06:27/ 0 赞/ 99 阅读

相关 STL初步：栈，队列和优先队列

集合栈计算机(The SetStack Computer）有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作： PUSH

一时失言乱红尘/ 2022年11月27日 12:15/ 0 赞/ 181 阅读

相关【LeetCode】栈、队列问题：优先队列

优先队列底层实现全部都是堆 jdk 提供了 `Queue<String> q = new PriorityQueue<>();`（注意：是小堆） [34

小鱼儿/ 2022年10月29日 09:12/ 0 赞/ 150 阅读

相关 leetcode——栈、队列、优先队列

题目 20. 有效的括号 150. 逆波兰表达式求值 71. 简化路径 144. 二叉树的前序遍历 9

左手的ㄟ右手/ 2022年10月13日 12:35/ 0 赞/ 167 阅读

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

Think: 1题意：模拟一个栈，有两种操作，栈顶增加一个元素，栈顶移除一个元素，要求元素按照编号大小移除，移除前可以选择是否调整栈内元素顺序，询问最少调整次数 2方法

野性酷女/ 2022年06月13日 03:52/ 0 赞/ 106 阅读

相关 821B - Okabe and Banana Trees——数学公式

Think: 1题意：沿着一条线段![这里写图片描述][SouthEast]，在这条线段下点可在线段上，找一个矩形，矩形的边分别与x轴，y轴平行，使得这个矩形的所有整数点的

ゝ一世哀愁。/ 2022年06月13日 03:52/ 0 赞/ 108 阅读

相关 Windows Message Queue————栈和队列（优先队列）

Message queue is the basic fundamental of windows system. For each process, the system m

﹏ヽ暗。殇╰゛Y/ 2022年05月18日 02:59/ 0 赞/ 171 阅读

相关 HDU1896 Stones————栈和队列(优先队列)

Because of the wrong status of the bicycle, Sempr begin to walk east to west every morni

拼搏现实的明天。/ 2022年05月18日 01:42/ 0 赞/ 199 阅读

相关栈/队列互相模拟实现

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。思路：大概这么想：用一个辅助栈把进第一个栈的元素倒一下就好了。比如进栈1，2，3，4

谁借莪１个温暖的怀抱￠/ 2022年05月12日 11:06/ 0 赞/ 141 阅读

相关 1498B - Box Fitting (优先队列)

[题目][Link 1] 思路：开一个优先队列存放每一行（高度1）还剩余的长度，将所有的木块从大到小排序，1开始遍历，如果优先队列中还能容纳最大的长度比当前木块大则加入到

ゝ一纸荒年。/ 2021年07月16日 11:45/ 0 赞/ 284 阅读