[题解] 洛谷 P3378 【模板】堆

P3378 【模板】堆

一、题意

维护一个初始为空的数列，支持三种操作：

对每个操作 2 输出一行答案。

二、怎么写？

题目显然是要用堆做的，我们可以建立一个小根堆并执行操作，完美符合题目的要求

但是为什么暴力过不了

• 插入：push_back，O(1)。
• 查最小：每次扫一遍，O(n)。
• 删最小：先扫出最小值的位置，再删除，O(n)。

单次 O(n)，总共 O(n^2)，n = 10^6 时约 10^12 次操作，大概率 TLE。

C++的STL里有堆这个数据结构，直接拿来用

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    priority_queue<long long, vector<long long>, greater<long long>> pq; // 构建小根堆
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int op;
        cin>>op;
        switch (op)
        {
        case 1:
            long long t;
            cin >>t;
            pq.push(t); // 向堆内加入元素
            break;
        case 2:
            cout<<pq.top()<<'\n'; //输出根节点（最小值）
            break;
        case 3:
            pq.pop(); //弹出堆顶（最小值）
            break;
        default:
            break;
        }
    }
    return 0;
}

三、关于堆

懒得写了先欠着