手打的小根堆怎么错了?求解答
查看原帖
手打的小根堆怎么错了?求解答
463562
Dreamerlee✅楼主2021/3/24 22:19

只得了44分

#include <iostream>
#include <cstdio>/*手打小根堆*/
#define ll long long
using namespace std;
ll heap[1000010], siz, now, n;
inline ll read()//快读
{
	ll x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + ch - '0';
		ch = getchar();
	}
	return x * f;
}
void swap(ll& a, ll& b)//交换函数
{
	ll t;
	t = a;
	a = b;
	b = t;
}
void add(ll x)//添加元素进堆
{
	heap[++siz] = x;
	now = siz;
	while (now)//如果不到根节点
	{
		ll father = now >> 1;//找他的父节点
		if (heap[father] > heap[now])//如果父节点大于子节点就换
			swap(heap[father], heap[now]);
		else
			break;//否则堆稳定,不用换
		now = father;//赋值,寻找下一个可以交换的父节点
	}
}
void pop()//删除堆最小的元素
{
	swap(heap[1], heap[siz]);//首先堆顶和堆尾交换
	--siz;//size--
	ll now = 1;
	while ((now << 1) <= siz)//对该节点进行向下交换的操作 
	{
		 ll nxt = now << 1;//找出当前节点的左儿子 
		if (heap[nxt + 1] <= siz && heap[nxt + 1] < heap[nxt])//看看是要左儿子还是右儿子跟它换 
			++nxt;
		if (heap[nxt] < heap[now])//如果不符合堆性质就换 
			swap(heap[now], heap[nxt]);
		else
			break;//否则完成
		now = nxt;//往下一层继续向下交换 
	}
}
int main()
{
	ll p, x;
	n = read();
	for (int i = 1; i <= n; i++)
	{
		p = read();
		switch (p)
		{
		case 1:
		{
			x = read();
			add(x);
			break;
		}
		case 2:
		{
			cout << heap[1] << endl;//因为堆是一直维护着的,所以只需输出第一个元素就是最小的
			break;
		}
		case 3:
		{
			pop();
			break;
		}
		}
	}
	return 0;
}
```cpp
2021/3/24 22:19
加载中...