题解 P1456 【Monkey King】

cjh20090318 · 2022-05-10 19:43:34 · 题解

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

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

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

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

下面……

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

有 N 只猴子，于是我们就要创建 N 个大根堆。
还需要长度为 N 的 father 数组，用来储存猴子的根，fa_i 表示第 i 个猴子的根。
当两只猴子打斗时，可以通过并查集的找根（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]);
}

根据题意，如果根相等（也就是互相认识），则输出 -1；否则从两只猴子的团队中取出（top&pop）强壮最大值（堆顶），分别除以 2 后再放回堆中（push）。
接着用并查集进行按秩合并（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());
        }
    }
}

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

谢谢查看！

此题是本人 AC 的第一道紫题，更是本人写的第一篇题解！