csp信奥赛C++标准模板库STL案例应用18
priority_queue实践
题目描述
给定一个数列，初始为空，请支持下面三种操作：
- 给定一个整数x xx，请将x xx加入到数列中。
- 输出数列中最小的数。
- 删除数列中最小的数（如果有多个数最小，只删除1 11个）。
输入格式
第一行是一个整数，表示操作的次数n nn。
接下来n nn行，每行表示一次操作。每行首先有一个整数o p opop表示操作类型。
- 若o p = 1 op = 1op=1，则后面有一个整数x xx，表示要将x xx加入数列。
- 若o p = 2 op = 2op=2，则表示要求输出数列中的最小数。
- 若o p = 3 op = 3op=3，则表示删除数列中的最小数。如果有多个数最小，只删除1 11个。
输出格式
对于每个操作2 22，输出一行一个整数表示答案。
输入输出样例 1
输入 1
5 1 2 1 5 2 3 2输出 1
2 5【数据规模与约定】
- 对于30 % 30\%30%的数据，保证n ≤ 15 n \leq 15n≤15。
- 对于70 % 70\%70%的数据，保证n ≤ 10 4 n \leq 10^4n≤104。
- 对于100 % 100\%100%的数据，保证1 ≤ n ≤ 10 6 1 \leq n \leq 10^61≤n≤106，1 ≤ x < 2 31 1 \leq x \lt 2^{31}1≤x<231，o p ∈ { 1 , 2 , 3 } op \in \{1, 2, 3\}op∈{1,2,3}。
思路分析
这是一个标准的**最小堆（小根堆）**实现问题。题目要求维护一个动态数列，支持三种操作：
- 插入元素
- 查询最小元素
- 删除最小元素
这种需求刚好可以用优先队列（堆）数据结构来实现。由于C++ STL中的priority_queue默认是大根堆，我们需要通过指定比较函数greater<int>来将其转换为小根堆。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,op,x;// 定义小根堆：使用优先队列，第三个参数 greater<int> 表示较小的元素优先级更高priority_queue<int,vector<int>,greater<int>>pq;intmain(){// 读入操作次数cin>>n;// 处理n次操作while(n--){cin>>op;// 读入操作类型if(op==1){// 操作1：插入元素cin>>x;// 读入要插入的值pq.push(x);// 将x压入小根堆}elseif(op==2){// 操作2：查询最小值// 输出堆顶元素（即最小值）cout<<pq.top()<<endl;}else{// 操作3：删除最小值pq.pop();// 弹出堆顶元素（即最小值）}}return0;}功能分析
1.数据结构选择
- 使用
priority_queue<int, vector<int>, greater<int>>实现小根堆 greater<int>比较器使得较小的整数具有更高的优先级- 堆的插入、删除、查询操作时间复杂度都是O(log n)
2.时间复杂度
- 操作1（插入）：O(log n)，堆的插入操作
- 操作2（查询最小值）：O(1)，直接访问堆顶
- 操作3（删除最小值）：O(log n)，弹出堆顶后需要调整堆结构
- 总体：对于n ≤ 10⁶的数据规模，O(n log n)的复杂度可以接受
3.空间复杂度
- O(n)，需要存储所有插入的元素
4.算法优势
- 高效：堆的插入和删除操作都只需要O(log n)时间
- 简洁：利用STL库，代码非常简洁
- 正确：保证了每次都能快速获取和删除最小值
完整系列资料，请查看专栏：《csp信奥赛C++标准模板库STL》
https://blog.csdn.net/weixin_66461496/category_13108077.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
- 2025 csp-j 复赛真题及答案解析（最新更新）
- 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
- 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
- 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
- 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
- 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
- 2020 ~ 2024 csp 复赛真题题单及题解
- 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
- 2021 ~ 2024 csp-s 初赛高频考点解析
- 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
- 2024 csp-j 初赛真题及答案解析
- 2025 csp-j 初赛真题及答案解析（最新更新）
- 2025 csp-s 初赛真题及答案解析（最新更新）
- 2025 csp-x (山东)初赛真题及答案解析(最新更新)
- 2025 csp-x (江西)初赛真题及答案解析(最新更新)
- 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
- 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图
4、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
