萌新第一次手打堆,36pts求调!!
查看原帖
萌新第一次手打堆,36pts求调!!
1042404
kuuuun楼主2024/8/8 09:30

代码如下 AC1,2,11,12AC1,2,11,12 剩下全 wawa

#include<bits/stdc++.h>
using namespace std;
int n,p,x;
struct heap
{
	int size;
	vector<int>v;
	void set(){size=0,v.push_back(0);}
	void pop()
	{
		swap(v[1],v[size]);
		v.pop_back(),size--;
		int i=1,net=2;
		if(net+1<=size&&v[net+1]<v[i])net++;
		while(v[net]<v[i]&&net<=size)
		{
			swap(v[net],v[i]);
			i=net;
			net<<=1;
			if(net+1<=size&&v[net+1]<v[i])net++;
		}
		return;
	}
	void push(int x)
	{
		v.push_back(x),size++;
		int i=size,net=(size>>1);
		while(v[net]>v[i]&&net)
		{
			swap(v[net],v[i]);
			i=net;
			net>>=1;
		}
		return;
	}
	int top()
	{
		return v[1];
	}
}q;
int main()
{
	scanf("%d",&n);
	q.set();
	while(n--)
	{
		scanf("%d",&p);
		if(p==1)
		{
			scanf("%d",&x);
			q.push(x);
		}
		if(p==2)printf("%d\n",q.top());
		if(p==3)q.pop();
	}
	return 0;
}
2024/8/8 09:30
加载中...