题解 P1456 【Monkey King】
这一道题就是使用的正常的可并堆
可并堆就是可以合并的堆
在合并前后都可以保持堆的性质，可以是小根堆也可以是大根堆。
so
我们要使用一些神奇的数据结构来维护这些堆
目前可以维护可并堆的有：左偏树，斜堆……
其实还有很多我就不一一介绍了
今天我们来探讨一下左偏树
这道题题面意思是给每个猴子和他认识的人一起维护一个大根堆；
然后每一次修改就是将两个大根堆的堆顶取出，并将战斗力除以二，
插入合并的两个堆中；
所以我们需要维护左偏树。
int hebing (int a,int b)
{
if(!a)return b;//如果有一个是空堆就返回
if(!b)return a;
if(key[a]<key[b])swap(a,b);//保持左偏树性质
rc[a]=hebing(rc[a],b);//迭代向下合并
if(date[rc[a]]>date[lc[a]])swap(lc[a],rc[a]);//继续维持性质
date[a]=date[rc[a]]+1;//进行合并
return a;//返回合并后的一共大小
}这是左偏树的核心代码
十分明（通）了（俗）简（易）洁（懂）；
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int lc[maxn],rc[maxn],date[maxn],key[maxn],fa[maxn];
int hebing (int a,int b)
{
if(!a)return b;//如果有一个是空堆就返回
if(!b)return a;
if(key[a]<key[b])swap(a,b);//保持左偏树性质
rc[a]=hebing(rc[a],b);//迭代向下合并
if(date[rc[a]]>date[lc[a]])swap(lc[a],rc[a]);//继续维持性质
date[a]=date[rc[a]]+1;//进行合并
return a;//返回合并后的一共大小
}
int ff(int x)//寻找父亲
{
return (fa[x]==x)?x:ff(fa[x]);
/*
相当于
if(fa[x]!=x)return ff(fa[x]);
else return x;
*/
}
inline int read(){//读入优化
int 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^48);
ch=getchar();
}
return x*f;
}
void work(int a,int b)//根据题目来完成输出
{
if((a=ff(a))==(b=ff(b)))//特判
{
cout<<"-1"<<endl;
return ;
}
//合并
//只要看懂核心代码就可以明白
fa[b]=a;
int art;
int rt;
int brt;
key[a]>>=1;
rt=hebing(lc[a],rc[a]);
lc[a]=rc[a]=date[a]=0;
art=hebing(a,rt);
fa[rt]=fa[a]=art;
key[b]>>=1;
rt=hebing(lc[b],rc[b]);
lc[b]=rc[b]=date[b]=0;
brt=hebing(b,rt);
fa[rt]=fa[b]=brt;
rt=hebing(art,brt);
fa[art]=fa[brt]=rt;
printf("%d\n",key[rt]);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{for(int i=1;i<=n;i++)
{
lc[i]=rc[i]=date[i]=0;
fa[i]=i;
key[i]=read();
}
int m=read();
for(int i=1;i<=m;i++)
{
work(read(),read());
}
}
return 0;
}这道题就这样完成了