社区讨论

零分求助!!

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 条回复,欢迎继续交流。

正在加载回复...