HDUOJ 1512 Monkey King

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1512

题意:n个猴子,一开始每个猴子只认识自己。每个猴子有一个力量值,力量值越大表示这个猴子打架越厉害。如果2个猴子不认识,他们就会找他们认识的猴子中力量最大的出来单挑,单挑不论输赢,单挑的2个猴子力量值减半,这2拨猴子就都认识了。现在给m组询问,如果2只猴子相互认识,输出-1,否则他们各自找自己认识的力量值最高的猴子单挑,求挑完后这拨猴子力量最大值。

思路:左偏树裸题。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,m,fa[maxn],l[maxn],r[maxn],d[maxn],v[maxn];
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
int Merge(int x,int y){
    if (!x) return y;
    if (!y) return x;
    if (v[x]<v[y]) swap(x,y);
    r[x]=Merge(r[x],y);
    fa[r[x]]=x;
    if (d[r[x]]>d[l[x]]) swap(l[x],r[x]);
    d[x]=d[r[x]]+1;
    return x;
}
int pop(int x){
    int L=l[x],R=r[x];
    fa[L]=L,fa[R]=R;
    l[x]=r[x]=d[x]=0;
    return Merge(L,R);
}
int main(){
    while (~scanf("%d",&n)){
        for (int i=1;i<=n;i++) read(v[i]),fa[i]=i,l[i]=r[i]=d[i]=0;
        d[0]=-1;
        for (read(m);m--;){
            int x,y;read(x),read(y);
            int tx=Find(x),ty=Find(y);
            if (tx==ty) puts("-1");
            else{
                int rootx=pop(tx),rooty=pop(ty);
                v[tx]/=2,v[ty]/=2;
                rootx=Merge(rootx,tx);
                rooty=Merge(rooty,ty);
                int tmp=Merge(rootx,rooty);//两堆合并后的根节点
                fa[rootx]=fa[rooty]=tmp;//更新fa
                printf("%d\n",v[tmp]);
            }
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注