标签:左偏树&并查集
思路来源
Q1:为什么用并查集?
A1:因为要判断两队猴子是否认识,在此处使用并查集可以便于维护两队猴子间的关系。
Q2:为什么用堆?
A2:因为每次对战都需要查找当前两队猴子中能力值最大的猴子,这里使用堆可以便于选出首领。
Q3:用什么样的堆?
A3:因为需要在两队猴子争执之后将两队猴子合并,并且不能破坏堆,所以要使用可并堆。
Q4:用什么可并堆?
A4:左偏树,斐波那契堆都是不错的可并堆,这里我使用的是左偏树。
具体做法
- 使用并查集维护两队猴子之间的关系,在争执前先特判两队猴子已经认识的情况。
- 根据题目要求,用左偏树模拟合并过程即可。
参考代码
#include<iostream> #include<cstdio> using namespace std; struct monkey { int lson;//用下标模拟地址 int rson;//用下标模拟地址 int power;//能力值 int dist;//节点到离它最近的外节点的距离(备注:外节点为叶节点或只有左(右)子树的节点) }m[100005]; int f[100005]; int ff(int ele) {//并查集-路径压缩 if (ele==f[ele]) { return ele; } return f[ele]=ff(f[ele]); } int merge(int ele1,int ele2) {//合并两个左偏树,并返回新书的根节点 if (ele1==0) {//如果有一棵待合并的树为空树,则合并结果为另一棵树 return ele2; } if (ele2==0) {//同上 return ele1; } if (m[ele1].power<m[ele2].power) {//保证第一棵树的能力值<第二颗树 swap(ele1,ele2); } m[ele1].rson=merge(m[ele1].rson,ele2);//将较小的树合并到较大树的右子树中 f[m[ele1].rson]=ele1; if (m[ele1].rson==0) {//更新根节点到离它最近的外节点的距离 m[ele1].dist=0; } else { m[ele1].dist=m[m[ele1].rson].dist+1; } if (m[m[ele1].lson].dist<m[m[ele1].rson].dist) {//根据左偏树的性质,当左侧的长度>右侧的长度时,要交换左右子树 swap(m[ele1].lson,m[ele1].rson); } return ele1; } int main() { int n,t,x,y,p,q,root,newx,newy; while (scanf("%d",&n)!=EOF) { for (register int i=1;i<=n;++i) { scanf("%d",&m[i].power); } for (register int i=1;i<=n;++i) {//在最初的时候,每只猴子独立形成一个群体 m[i].lson=0; m[i].rson=0; f[i]=i; } scanf("%d",&t); while (t--) { scanf("%d%d",&x,&y); p=ff(x);//找出各自的首领,这部分用并查集维护 q=ff(y); if (p==q) {//按题目要求,两只本来就认识的猴子不会发生争执 printf("-1\n"); continue; } m[p].power/=2;//更新首领在争执后剩余的能力值 root=merge(m[p].lson,m[p].rson);//先合并原首领的左右子树 m[p].lson=0;//将首领孤立 m[p].rson=0; newx=merge(root,p);//让首领归队,这部分用左边数维护,以便选出首领 m[q].power/=2;//同上 root=merge(m[q].lson,m[q].rson); m[q].lson=0; m[q].rson=0; newy=merge(root,q); root=merge(newx,newy);//将争执后的两队猴子合并 f[newx]=root;//更新并查集 f[newy]=root; printf("%d\n",m[root].power);//输出新首领的能力值 } } return 0; }