做一道左偏堆复习一下0 0.
左偏堆比普通的堆多存一个dis值,他有几个性质,节点dis=右儿子dis+1,左儿子dis > = 右儿子dis,然后就是一些标准操作了,每次合并在右儿子上插就没了。
这个题目题意如下【题目大意】
在一个森林里住着N(N<=100000)只猴子。在一开始,他们是互不认识的。但是随着时间的推移,猴子们少不了争斗,但那只会发生在互不认识(认识具有传递性)的两只猴子之间。争斗时,两只猴子都会请出他认识的猴子里最强壮的一只(有可能是他自己)进行争斗。争斗后,这两只猴子就互相认识。每个猴子有一个强壮值,但是被请出来的那两只猴子进行争斗后,他们的强壮值都会减半(例如10会减为5,5会减为2)。现给出每个猴子的初始强壮值,给出M次争斗,如果争斗的两只猴子不认识,那么输出争斗后两只猴子的认识的猴子里最强壮的猴子的强壮值,否则输出 -1。
左偏堆裸题,很好想思路,最开始每只猴子是一个堆,每次争斗就合并,加一个并查集就好了。
ac代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#define N 100005
using namespace std;
int n,m,fa[N],x,p,q;
struct Node{
int dis,val;
Node *ls,*rs;
};
Node pool[4*N],*tail=pool,*root[N];
int dis(Node *nd){return nd==NULL?0:nd->dis;}
void update(Node *nd){
if(dis(nd->ls)<dis(nd->rs))
swap(nd->ls,nd->rs);
nd->dis=dis(nd->rs)+1;
}
Node *newnode(int val){
Node *nd=++tail;
nd->val=val;
nd->dis=1;
nd->ls=nd->rs=NULL;
return nd;
}
Node *merge(Node *a,Node *b){
if(a==NULL)return b;
if(b==NULL)return a;
if(a->val<b->val)swap(a,b);
a->rs=merge(a->rs,b);
update(a);
return a;
}
Node *del(Node *a){return a==NULL?a:merge(a->ls,a->rs);}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
while(~scanf("%d",&n)){
tail=pool;
for(int i=1;i<=n;i++){
scanf("%d",&x);
fa[i]=i;
root[i]=newnode(x);
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&p,&q);
int x=find(p),y=find(q);
if(x==y) printf("-1\n");
else{
fa[y]=x;
int xx=root[x]->val/2,yy=root[y]->val/2;
root[x]=del(root[x]);root[y]=del(root[y]);
root[x]=merge(root[x],newnode(xx));
root[y]=merge(root[y],newnode(yy));
root[x]=merge(root[x],root[y]);
printf("%d\n",root[x]->val);
}
}
}
return 0;
}
版权声明:本文为Kamisama123原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。