WA 36pts 求调
查看原帖
WA 36pts 求调
656427
iamsh楼主2024/11/25 20:37

rt,想封装一个堆,交上去发现 #3 ~ #10 都错了

#include<bits/stdc++.h>
using namespace std;
template<typename T,int N> struct Heap {
	T h[N];
	int tot = 0;
	int size() {
		return tot;
	}
	void push(T x) {
		h[++ tot] = x;
		int now = tot;
		while(now >> 1) {
			int nxt = now >> 1;
			if(h[now] < h[nxt]) {
				swap(h[now],h[nxt]);
				now = nxt;
			}
			else {
				break;
			}
		}
	}
	void pop() {
		swap(h[1],h[tot]);
		tot --;
		int now = 1;
		while((now << 1) <= tot) {
			int lson = now << 1,rson = now << 1 | 1,nxt;
			if(rson <= tot && h[lson] < h[rson]) {
				nxt = rson;
			}
			else {
				nxt = lson;
			}
	        if(h[nxt] < h[now]) {
	        	swap(h[nxt],h[now]);
	        	now = nxt;
			}
	        else {
	        	break;
			}
		}
	}
	T top() {
		return h[1];
	}
};
Heap<int,int(1e6 + 5)> h;
int main() {
	int q;
	scanf("%d",&q);
	while(q --) {
		int op,x;
		scanf("%d",&op);
		if(op == 1) {
			scanf("%d",&x);
			h.push(x);
		}
		else if(op == 2) {
			printf("%d\n",h.top());
		}
		else {
			h.pop();
		}
	}
}
2024/11/25 20:37
加载中...