请问这个写法是错的吗?复杂度应该最多就是nlogn呀,为什么会TLE+WA?
查看原帖
请问这个写法是错的吗?复杂度应该最多就是nlogn呀,为什么会TLE+WA?
261262
WaltVBAlston楼主2020/10/24 11:21

如题,昨天和学长打赌能不能写出来这道题,他折腾了半天92,,我一看不会写堆,5分钟随便写了个优先队列过了把学长气个半死

今天想手写一下,但是貌似写错了,WA+TLE,#11TLE,#1、2、3、12AC,其他全部WA,求助!

#include<cstdio>
using namespace std;
int p,tree[1000005],t,x,size=0;
void heapify(int i){
	int L=i*2,R=i*2+1,maxn=i;
	if(L<=size&&tree[L]<tree[maxn])
		maxn=L;
	if(R<=size&&tree[R]<tree[maxn])
		maxn=R;
	if(maxn!=i){
		int t=tree[i];
		tree[i]=tree[maxn];
		tree[maxn]=t;
		heapify(maxn);
	}
	return;
}
void build(int type2){
	for(int i=size/2;i>=1;i--)
		heapify(i);
	if(type2==2)
		size--;
	return;
}
int main(){
	//freopen("P3378_4.in","r",stdin);
	//freopen("rrr.in","w",stdout);
	scanf("%d",&p);
	while(p--){
		scanf("%d",&t);
		if(t==1){
			scanf("%d",&x);
			size++;
			tree[size]=x;
			build(1);
		}
		else if(t==2){
			printf("%d\n",tree[1]);
		}
		else{
			tree[1]=10000005;
			build(2);
		}
	}
	return 0;
}
2020/10/24 11:21
加载中...