如果你配对堆44pts
查看原帖
如果你配对堆44pts
85994
嘉年华楼主2024/6/26 20:33

pop\text{pop} 之后配对要重新导向堆顶,特判只有一个儿子的情况:

int EraseNode(int root) {
	static std::queue<int> node_list;  //临时存放所有儿子
	for(int x:node_[root].son_) {
		node_list.push(x);
		node_[x].fa_=-1;
		node_[x].top_=x;
	}  //先将所有儿子放下来
	node_[root].son_.clear();
	int x(0),y(0),z(0);
	while(node_list.size()>1u) {
		x=node_list.front();
		node_list.pop();
		y=node_list.front();
		node_list.pop();  //每次取出两个节点配对合并
		node_[root].top_=z=MergeId(x,y);  //将top_指向新的根,保证路径压缩的正确性
		node_list.push(z);  //连续配对
	}
	if(!node_list.empty()) {
		node_[root].top_=node_list.front();
		node_list.pop();
	}  //可能原本就只有一个儿子
	return node_[root].top_;//返回新的根
}  //删除root这个节点(不一定是根)

删去最后的 if\text{if} 中第一句对 top_\text{top\_} 的赋值会导致 WA on Sub1# 6-12,Sub2# 1。

2024/6/26 20:33
加载中...