HDU 1512 Monkey King（左偏树）

蔚落 2022-06-08 09:51 149阅读 0赞

题目链接：  
[HDU 1512][]

题意：  
有 n 只猴子，每只猴子都有一个力量，开始时互相都不认识，它们之间发生 m 次争斗，每次发生a,b发生争斗时，a,b会从它们认识的猴子中选出一个最强的，并变为这两只猴子发生争斗，打完之后这两个猴子就互相认识，并且力量减半，如果a,b互相认识就输出−1，否则输出认识的猴子中最大的力量值。

题解：  
左偏树。

AC代码：

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct node
    {
        int l,r;
        int dis;
        int val;
    }ltree[100005];
    int par[100005];
    int getfather(int x)
    {
        return par[x] == x?x:par[x]=getfather(par[x]);
    }
    int merge(int x,int y)//返回合并后的根
    {
        int l,r;
        //插入的树为空时直接返回x (y)，也就是合并完的树
        if(x==0)return  y;
        if(y==0)return  x;
        if(ltree[x].val<ltree[y].val)  //大顶堆
        {
            swap(x,y);
        }
        ltree[x].r = merge(ltree[x].r,y);//递归合并右子树 和 y
        l = ltree[x].l;
        r = ltree[x].r;
        par[r] = x; //并查集合并，更新右子树的根 
    
        if(ltree[l].dis<ltree[r].dis)
        {
            //必须遵守左偏树的性质，左节点的距离不小于右节点的距离
            swap(ltree[x].l,ltree[x].r);
        }
        if(ltree[x].r==0)//如果没有右子树 则距离为0
        {
            ltree[x].dis = 0;
        } 
        else ltree[x].dis = ltree[ltree[x].r].dis+1;
        return x;
    }
    int pop(int x)//返回删除根以后左右子树合并的根
    {
        int l,r;
        l = ltree[x].l;
        r = ltree[x].r;
        //因为要暂时删掉根，所以左右子树先作为根  
        par[l] = l;
        par[r] = r;
        ltree[x].l = 0;
        ltree[x].r = 0;
        ltree[x].dis = 0;
        return merge(l,r); 
    }
    int main()
    {
        int n,m;
        while(cin>>n)
        {
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&ltree[i].val);
                ltree[i].l = 0;
                ltree[i].r = 0;
                ltree[i].dis = 0;
            }
            for(int i=1;i<=n;i++)par[i] = i;
            scanf("%d",&m);
            int a,b;
            int fa,fb;
            int l,r;
            while(m--)
            {
    
                scanf("%d%d",&a,&b);
                fa = getfather(a);
                fb = getfather(b);
                if(fa==fb)puts("-1");
                else
                {
                    //单挑后减半 
                    ltree[fa].val /= 2;
                    ltree[fb].val /= 2;
                    //删除最大的两个值，再与新的值合并 
                    l = pop(fa),r=pop(fb);
                    l = merge(l,fa);
                    r = merge(r,fb);
                    l = merge(l,r);
                    printf("%d\n",ltree[l].val); 
                }
            }
        }
        return 0;
    }

[HDU 1512]: http://acm.hdu.edu.cn/showproblem.php?pid=1512