（上一次更新： 2022-06-02 19:40 ，修改了乱加空格的问题，以及函数 merge 的命名）

大家好，我是 CQ-FZOIer，C2024 级蒟蒻 CJH。洛谷博客

最近我们学了堆，接着学了并查集，老师就为我们布置了这一道题目 Monkey King 了。 我们还没有学左偏树，所以看不懂各位大佬的左偏树题解。 我决定换一种更浅显的方式，也就是……

堆+并查集的方法来 AC 此题！！！

下面……

开始切入正题，分析题目：

1. 有 $N$ 只猴子，于是我们就要创建 $N$ 个大根堆。
2. 还需要长度为 $N$ 的 father 数组，用来储存猴子的根，$fa_i$ 表示第 $i$ 个猴子的根。
3. 当两只猴子打斗时，可以通过并查集的找根（find）来查找猴子的根：

int find(int x){//找猴子x的根
	//循环查找
	/*while(x!=fa[x]){
		x=fa[x];
	}
	return x;*/
	//递归查找
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}

4. 根据题意，如果根相等（也就是互相认识），则输出 $-1$；否则从两只猴子的团队中取出（top&pop）强壮最大值（堆顶），分别除以 $2$ 后再放回堆中（push）。
5. 接着用并查集进行按秩合并（merge）：

void merge(int x,int y){//合并x,y
	int f1=find(x),f2=find(y);//找到两只猴子的根
	if(f1==f2)//如果为同一个根
		printf("-1\n");
	else{
		int at=a[f1].top(),bt=a[f2].top();
		a[f1].pop();a[f2].pop();
		at/=2;bt/=2;//按照题目要求减少一半
		a[f1].push(at);a[f2].push(bt);//放回原堆中
		if(a[f1].size()<a[f2].size()){//按秩合并，减少循环次数。
			//合并
			fa[f1]=f2; 
			//将一对元素全部移至f2
			while(!a[f1].empty()){
				int tmp=a[f1].top();
				a[f1].pop();
				a[f2].push(tmp);
			}
			//输出最大值
			printf("%d\n",a[f2].top());
		}
		else{
			//同上
			fa[f2]=f1;
			while(!a[f2].empty()){
				int tmp=a[f2].top();
				a[f2].pop();
				a[f1].push(tmp);
			}
			printf("%d\n",a[f1].top());
		}
	}
}

注意事项

题目可能有多组数据！！！所以我们应该一直读入至文件结束符 EOF。

具体详见代码（请勿抄袭！！！）：

//the code is from chenjh
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[100001];//存储每只猴子的根
priority_queue <int> a[100001];//维护的堆
//函数都在后面！！！
int find(int x);//找根
void merge(int x,int y);//合并
int main(){
	while(scanf("%d",&n)!=EOF){//有多组数据，需要一直读入到文件结束符EOF
		//需要清空堆！
		for(int i=0;i<=100000;i++){
			while(!a[i].empty())
				a[i].pop();
		}
		//将根先设为自己
		for(int i=1;i<=n;i++) fa[i]=i;
		//读入实力值，存储至堆中
		for(int i=1;i<=n;i++){
			int x;
			scanf("%d",&x);
			a[i].push(x);
		}
		//进行打斗
		scanf("%d",&m);
		for(int i=1;i<=m;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			merge(x,y);//合并
		}
	}
	return 0;
}
int find(int x){
	//循环找根
	/*while(x!=fa[x]){
		x=fa[x];
	}
	return x;*/
	//递归找根
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	int f1=find(x),f2=find(y);//找到两只猴子的根
	if(f1==f2)//如果为同一个根
		printf("-1\n");
	else{
		int at=a[f1].top(),bt=a[f2].top();
		a[f1].pop();a[f2].pop();
		at/=2;bt/=2;//按照题目要求减少一半
		a[f1].push(at);a[f2].push(bt);//放回原堆中
		if(a[f1].size()<a[f2].size()){//按秩合并，减少循环次数。
			//合并
			fa[f1]=f2; 
			//将一对元素全部移至f2
			while(!a[f1].empty()){
				int tmp=a[f1].top();
				a[f1].pop();
				a[f2].push(tmp);
			}
			//输出最大值
			printf("%d\n",a[f2].top());
		}
		else{
			//同上
			fa[f2]=f1;
			while(!a[f2].empty()){
				int tmp=a[f2].top();
				a[f2].pop();
				a[f1].push(tmp);
			}
			printf("%d\n",a[f1].top());
		}
	}
}

如有错误，欢迎批评指正，本人将尽快修改。

谢谢查看！