洛谷题解——【模板】堆
2023-07-08 11:27:07   来源:博客园


(相关资料图)

题目链接:【模板】堆【模板】堆题目描述

给定一个数列,初始为空,请支持下面三种操作:

给定一个整数 \(x\),请将 \(x\) 加入到数列中。输出数列中最小的数。删除数列中最小的数(如果有多个数最小,只删除 \(1\) 个)。输入格式

第一行是一个整数,表示操作的次数 \(n\)。接下来 \(n\) 行,每行表示一次操作。每行首先有一个整数 \(op\) 表示操作类型。

若 \(op = 1\),则后面有一个整数 \(x\),表示要将 \(x\) 加入数列。若 \(op = 2\),则表示要求输出数列中的最小数。若 \(op = 3\),则表示删除数列中的最小数。如果有多个数最小,只删除 \(1\) 个。输出格式

对于每个操作 \(2\),输出一行一个整数表示答案。

样例 #1样例输入 #1
51 21 5232
样例输出 #1
25
提示

【数据规模与约定】

对于 \(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\}\)。这道题考察的是小顶堆的使用方法一:暴力求解(代码这里就不写了)方法二:手写堆
#includeusing 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])l=i*2;elsel=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;}elsef=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<
方法三:STL优先队列
#includeusing namespace std;int n,x;int main(){priority_queue ,greater > 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<

关键词:

上一篇:上能电气07月07日获深股通增持100.99万股
下一篇:最后一页