icontofig | 发布于 2019-08-03 20:58:54 | 阅读量 257 | 左偏树 并查集
发布于 2019-08-03 20:58:54 | 左偏树 并查集

题目大意

有n只猴子,每只猴子有自己的能力值,它们会有m次冲突,每次冲突若两只猴子不在同一阵营,则选出两只猴子所在阵营中能力值最高的猴子较量,能力值高的猴子会获胜,并且能力值减半,失败的一方加入胜利方的阵营,问每一次冲突获胜阵营出战的猴子在获胜后的能力值。若同一阵营则输出-1。

题解

每个阵营选出最大值,显然是要维护一个堆什么的,但是至于合并怎么办?

可并堆其实有很多种,这里感觉还是左偏树比较简单。

我们维护左偏树,每一个阵营对应一棵左偏树。

在发生一次冲突时,我们用并查集查询两只猴子所在阵营中能力值最大的猴子(在左偏树的维护过程中保证并查集的根即是左偏树的根),若在一个阵营,直接输出-1;若不在一个阵营,则直接合并两个左偏树,输出新的左偏树的根节点的能力值的二分之一后,将其能力值减半,并从左偏树中暂时删除,然后合并原先的左偏树的左子树和右子树,合并完以后再将刚刚删除的这个点并入新的左偏树,再生成一个左偏树,这个左偏树即是冲突后最新阵营的能力值大根堆了。

总的时间复杂度为O(mlogn)

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
int f[maxn];
int hp[maxn],d[maxn],val[maxn],l[maxn],r[maxn];
int find(int x){
    if(f[x] != x) f[x] = find(f[x]);
    return f[x];
}
int n,m,a,b;
int merge(int a,int b){
    if(!a || !b)return a + b;
    if(val[a] < val[b]){
        swap(a,b);
    }
    r[a] = merge(r[a],b);
    f[r[a]] = a;
    if(d[r[a]] > d[l[a]])swap(l[a],r[a]);
    d[a] = d[r[a]] + 1;
    return a;
}
void solve(int x,int y){
    int p = find(x),q = find(y);
    if(p == q){
        printf("-1\n");
        return;
    }
    int t = merge(p,q);
    printf("%d\n",val[t] / 2);
    val[t] /= 2;
    f[l[t]] = l[t];
    f[r[t]] = r[t];
    int p1 = l[t],p2 = r[t];
    l[t] = 0;
    r[t] = 0;
    d[t] = 0;
    int k = merge(p1,p2);
    t = merge(t,k);
    return;
}
int main(){
    while(scanf("%d",&n) != EOF){
        for(int i = 1;i <= n;++i)
            val[i] = get_num();
        for(int i = 1;i <= n;++i){
            f[i] = i;
            l[i] = r[i] = d[i] = 0;
        }
        m = get_num();
        while(m--){
            a = get_num();
            b = get_num();
            solve(a,b);
        }
    }
    return 0;
}

 


内容更新于: 2019-08-03 20:59:03
链接地址: http://blog.leanote.com/post/icontofig/fb90f18e7fbc

上一篇: SPOJ SPOINTS - Separate Points 凸包+判断点与凸包、线段的位置

下一篇: Codeforces 965E Short Code Trie树+贪心(启发式合并)

257 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航