题解：洛谷 P3378 【模板】堆

【题目来源】

洛谷：P3378 【模板】堆 - 洛谷

【题目描述】

给定一个数列，初始为空，请支持下面三种操作：

1. 给定一个整数 \(x\)，请将 \(x\) 加入到数列中。
2. 输出数列中最小的数。
3. 删除数列中最小的数（如果有多个数最小，只删除 \(1\) 个）。

【输入】

第一行是一个整数，表示操作的次数 \(n\)。
接下来 \(n\) 行，每行表示一次操作。每行首先有一个整数 \(op\) 表示操作类型。

• 若 \(op = 1\)，则后面有一个整数 \(x\)，表示要将 \(x\) 加入数列。
• 若 \(op = 2\)，则表示要求输出数列中的最小数。
• 若 \(op = 3\)，则表示删除数列中的最小数。如果有多个数最小，只删除 \(1\) 个。

【输出】

对于每个操作 2，输出一行一个整数表示答案。

【输入样例】

5
1 2
1 5
2
3
2

【输出样例】

2
5

【算法标签】

《洛谷 P3378 堆》 #堆# #O2优化#

【代码详解】

#include <bits/stdc++.h>
using namespace std;int n;  // 操作次数
priority_queue<int, vector<int>, greater<int>> q;  // 小根堆（最小值优先）int main()
{// 输入操作次数cin >> n;// 处理每个操作for (int i = 1; i <= n; i++){int op, x;cin >> op;  // 输入操作类型if (op == 1)  // 操作1：插入元素{cin >> x;q.push(x);  // 将x插入堆中}else if (op == 2)  // 操作2：查询最小值{cout << q.top() << endl;  // 输出堆顶元素（最小值）}else if (op == 3)  // 操作3：删除最小值{q.pop();  // 删除堆顶元素（最小值）}}return 0;
}

【运行结果】

5
1 2
1 5
2
2
3
2
5