P3378 【模板】堆
题目简述
给定三个操作,求数列中最小的数,删除数列中最小的数,插入一个新的数
思路
板子题没什么好说,用 stl 自带的优先队列很好写,但手写的也要掌握。
建议参考这篇博客
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int tr[N];
int main(){
int n,len=0;
cin>>n;
while(n--){
int op;
cin>>op;
switch(op){
case 1:{
int x;
cin>>x;
tr[++len]=x;
int kdl=len;
while(kdl){
if(tr[kdl>>1]>tr[kdl])tr[kdl>>1]^=tr[kdl]^=tr[kdl>>1]^=tr[kdl];
else break;
kdl>>=1;
}
break;
}
case 2:{
cout<<tr[1]<<endl;
break;
}
case 3:{
int kdl=1;
tr[len]^=tr[1]^=tr[len]^=tr[1];
tr[len]=0;
len--;
while(kdl<len){
int ls=(kdl<<1),rs=(kdl<<1|1);
if(ls>len){
break;
}
if(rs>len){
if(tr[ls]<tr[kdl])tr[kdl]^=tr[ls]^=tr[kdl]^=tr[ls];
break;
}
if(tr[ls]<tr[rs]){
if(tr[ls]<tr[kdl])tr[kdl]^=tr[ls]^=tr[kdl]^=tr[ls],kdl=ls;
else break;
}
else {
if(tr[rs]<tr[kdl])tr[kdl]^=tr[rs]^=tr[kdl]^=tr[rs],kdl=rs;
else break;
}
}
break;
}
}
}
return 0;
}
PS:有时候真的很奇怪我是怎么能把代码都写这么冗长的/kk