不知道起什么题目好

· · 题解

前置知识

首先看到要取出最小值，那么一定就是优先队列了。

优先队列

思路

由于输出的是最小值，所以我们要用到的是小根堆，定义有稍许不同。

priority_queue<int,vector<int>,greater<int>>q;

解决了优先队列看到他还有修改操作，要是整体修改肯定是会超时的，所以我们可以想到一个类似于前缀和的算法。

如果把每一次添加的数当做一个数组，那么我们可以得出一个数所增加的值一定是它添加之后增加的数到他取出前的数的前缀和，那么我们可以找到规律，如果一个数添加上目前增加的所有的数，那么它比真正的值所大的就是他之前的数的总和，那么由此我们可以判断出，每一次添加一个数的时候，我们可以添加这个数减去之前增长的值，这样一来可以快速记录当前的值，同时我们也更好地维护优先队列中数的顺序。（如果没有看懂就看代码吧）

CODE：

#include<bits/stdc++.h>
using namespace std;
//十年OI一场空，不开long long见祖宗 
priority_queue<long long,vector<long long>,greater<long long>> q;
long long cnt,n,x;//cnt统计一共加了多少数 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //前三行是加快cincout速度的
    //本人懒得写scanf与快读 
    cin>>n;
    for(int i=1,h;i<=n;i++){
        cin>>h;
        if(h==1){
            cin>>x;
            q.push(x-cnt);
        }
        else if(h==2){
            cin>>x;
            cnt+=x;
        }
        else {
            cout<<q.top()+cnt<<"\n";
            //换行使用'\n'速度更快 
            q.pop();
        }
    }
    return 0;
    //return 0;是好习惯 
}