社区讨论
零分求助!!
P3378【模板】堆参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @m3a3o7fs
- 此快照首次捕获于
- 2024/11/09 19:46 去年
- 此快照最后确认于
- 2025/11/04 15:02 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
int heap[50000],top = 0,n;
struct s{
int op;
int x;
}c[1000010];
void push(int x)
{
top++;
int p = top;
while (p > 1) {
if (heap[p/2] < x) {
break;
}
heap[p] = heap[p/2];
p = p / 2;
}
heap[p] = x;
}
int pop() {
heap[0] = heap[1];
int x = heap[top];
top--;
int fa = 1;
while (fa*2 <= top) {
int son = fa*2;
if (heap[son+1] < heap[son]) son++;
if (heap[son] > x) break;
heap[fa] = heap[son];
fa = son;
}
heap[fa] = x;
return heap[0];
}
void dlt() {
int x = heap[top];
int fa = 1;
while (fa*2 <= top) {
int son = fa*2;
if (heap[son+1] < heap[son]) son++;
if (heap[son] > x) break;
heap[fa] = heap[son];
fa = son;
}
}
int main()
{
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> c[i].op;
if (c[i].op == 1) {
cin >> c[i].x;
}
}
for (int i = 1;i <= n;i++) {
if (c[i].op == 1) {
push(c[i].x);
}
else if (c[i].op == 3) {
dlt();
}
else if (c[i].op == 2) {
cout << pop() << endl;
}
}
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...