P76061 维护最小值 — 题解

专题： STL
适用题目： 新生 OJ 本地题包中的 P76061，不要直接用于外站同名题。

解题思路

用 priority_queue<long long, vector<long long>, greater<long long>> 维护小根堆，支持插入、输出堆顶、删除堆顶。

复杂度

插入和删除 $O(\log n)$，查询最小值 $O(1)$。

易错点

默认 priority_queue 是大根堆，需要指定 greater。

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin>>q;
    priority_queue<ll,vector<ll>,greater<ll>> h;
    while(q--){
        int typ;
        cin>>typ;
        if(typ==1){
            ll x;
            cin>>x;
            h.push(x);
        }
        else if(typ==2)cout<<h.top()<<nl;
        else h.pop();
    }
    return 0;
}

为什么只提供 C++： 本题专题要求使用 STL 容器或算法，C 语言没有 STL；C 可以用手写数据结构解决，但不属于本专题的教学目标。

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。