題目大意

如題，初始小根堆為空，我們需要支持以下3種操作：

操作1： 1 x 表示將x插入到堆中

操作2： 2 輸出該小根堆內(nèi)的最小數(shù)

操作3： 3 刪除該小根堆內(nèi)的最小數(shù)

輸入格式

第一行包含一個(gè)整數(shù)N，表示操作的個(gè)數(shù)

接下來N行，每行包含1個(gè)或2個(gè)正整數(shù)，表示三種操作，格式如下：

操作1： 1 x

操作2： 2

操作3： 3

輸出格式：

包含若干行正整數(shù)，每行依次對(duì)應(yīng)一個(gè)操作2的結(jié)果。

輸入樣例

5

1 2

1 5

2

3

2
輸出樣例

2

5

---

code

#include<bits/stdc++.h> using namespace std;const int N = 1e6+5; int n,i,t,x,tot = 0,now,nxt; int v[N];inline int read() {int x = 0;char ch =getchar();while(ch < '0' || ch > '9') ch = getchar();while(ch >='0' && ch <= '9'){x = x*10 + ch-'0';ch = getchar();}return x; }inline void insert() {x = read();v[++tot] = x;now = tot;while(v[now>>1] > v[now]) {swap(v[now>>1] , v[now]);now = now>>1;} }inline void del() {v[1] = v[tot--];now = 1;while((now<<1) <= tot){nxt = now<<1;if(nxt+1 <= tot && v[nxt+1] < v[nxt]) nxt++;if(v[nxt] < v[now]) swap(v[now],v[nxt]);else break;now = nxt; } }int main() {n = read();for(i = 1;i <= n;i++){t = read();if(t == 1) insert();if(t == 2) printf("%d\n",v[1]);if(t == 3) del();}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Mark-X/p/11404640.html

總結(jié)

以上是生活随笔為你收集整理的luogu P3378 【模板】堆的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。