题目链接:【模板】堆
【模板】堆
题目描述
给定一个数列,初始为空,请支持下面三种操作:
- 给定一个整数 \(x\),请将 \(x\) 加入到数列中。
- 输出数列中最小的数。
- 删除数列中最小的数(如果有多个数最小,只删除 \(1\) 个)。
输入格式
第一行是一个整数,表示操作的次数 \(n\)。
接下来 \(n\) 行,每行表示一次操作。每行首先有一个整数 \(op\) 表示操作类型。
- 若 \(op = 1\),则后面有一个整数 \(x\),表示要将 \(x\) 加入数列。
- 若 \(op = 2\),则表示要求输出数列中的最小数。
- 若 \(op = 3\),则表示删除数列中的最小数。如果有多个数最小,只删除 \(1\) 个。
输出格式
对于每个操作 \(2\),输出一行一个整数表示答案。
样例 #1
样例输入 #1
5
1 2
1 5
2
3
2
样例输出 #1
2
5
提示
【数据规模与约定】
- 对于 \(30\%\) 的数据,保证 \(n \leq 15\)。
- 对于 \(70\%\) 的数据,保证 \(n \leq 10^4\)。
- 对于 \(100\%\) 的数据,保证 \(1 \leq n \leq 10^6\),\(1 \leq x \lt 2^{31}\),\(op \in \{1, 2, 3\}\)。
这道题考察的是小顶堆的使用
方法一:暴力求解(代码这里就不写了)
方法二:手写堆
#include<bits/stdc++.h>
using namespace std;
long long n,heap[10000000],t=0;
void sup(int i){
int flag=0;
if(i==1)return ;
while(i!=1&&flag==0){
if(heap[i]<heap[i/2])
swap(heap[i],heap[i/2]);
else
flag=1;
i/=2;
}
}
void sdown(int i){
int l,f=0;
while(i*2<=t&&f==0){
if(heap[i]>heap[i*2])
l=i*2;
else
l=i;
if(i*2+1<=t){
if(heap[l]>heap[i*2+1])
l=2*i+1;
}
if(l!=i){
swap(heap[l],heap[i]);
i=l;
}else
f=1;
}
}
void del(int i){
heap[i]=heap[t];
t--;
sdown(i);
}
int main(){
cin>>n;
int op;
for(int i=1;i<=n;i++){
cin>>op;
if(op==1){
cin>>heap[++t];
sup(t);
}
if(op==2){
cout<<heap[1]<<endl;
}
if(op==3){
del(1);
}
}
return 0;
}
方法三:STL优先队列
#include<bits/stdc++.h>
using namespace std;
int n,x;
int main(){
priority_queue <int,vector<int>,greater<int> > q;
cin>>n;
int op;
for(int i=1;i<=n;i++){
cin>>op;
if(op==1){
cin>>x;
q.push(x);
}
if(op==2){
cout<<q.top()<<endl;
}
if(op==3){
q.pop();
}
}
return 0;
}
标签:洛谷,数列,int,题解,cin,leq,heap,模板,op
From: https://www.cnblogs.com/NightinGaleCode/p/17536945.html