BZOJ 1208 [HNOI2004]宠物收养所:Splay(伸展树)

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1208

题意:

  有一个宠物收养所,在接下来一段时间内会陆续有一些宠物进到店里,或是一些人来领养宠物。宠物和人的总数量为n。

  t = 0代表宠物,t = 1代表人。

  宠物和人分别有一个特点值a和b。有两种情况:

    (1)店里全是宠物,这时进来一个人来领养宠物。那么他会领养走abs(a-b)最小的那只宠物(b = a - x or a + x)。

      如果使得abs(a-b)最小的有不止一只宠物,那么b = a - x的那只会被领养走。

    (2)店里全是等待的人。这事有一只宠物被送进店里,那么它会被abs(a-b)最小的那个人领养走(a = b - x or b + x)。

      如果使得abs(a-b)最小的不只有一个人,那么宠物会被a = b - x的人领养走。

  按照依次来到店里的顺序,给出a,b。

  a = 0代表宠物,a = 1代表人。b为对应的特点值。

  定义每一次领养的不满意度 = abs(宠物特点值 - 人的特点值)

  问你所有不满意度之和 MOD 1000000。

题解:

  Splay。

  分析:

    (1)在每一个时刻(除了正在领养),店里要么全是宠物,要么全是人,要么为空。

    (2)在本题中,除了只能是人和宠物匹配这个特性,人和宠物是等价的,都可以在店里等待。

    (3)有可能先进来一大堆宠物,再进来一大堆人。这时搜索树会退化成链,所以要用splay。

  实现:

    每输入一对a,b:

    (1)如果店为空,那么将东西加入树中,并将树的类型改为a。

    (2)如果进来一个同类,那么将当前东西加入树中。

    (3)如果进来一个异类,那么找出对于这个异类的特点值的前驱pre与后继suc(类型均为pair<int,int>(dif,idx))。

      将被删除的东西为res = min(pre,suc)。

      所以erase(res.second),并更新答案ans = (ans + res.first) % MOD。

AC Code:

 #include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 80005
#define MOD 1000000
#define INF 100000000 using namespace std; int n,a,b;
int ans=;
int type;
int siz=;
int tot=;
int root=-;
int dat[MAX_N];
int par[MAX_N];
int lson[MAX_N];
int rson[MAX_N]; void rotate(int x,int type,int *lson,int *rson)
{
if(type==) swap(lson,rson);
int y=par[x];
int z=par[y];
lson[y]=rson[x];
if(rson[x]!=-) par[rson[x]]=y;
par[x]=z;
if(z!=-)
{
if(lson[z]==y) lson[z]=x;
else rson[z]=x;
}
rson[x]=y;
par[y]=x;
} void splay(int x,int act)
{
while(par[x]!=act)
{
int y=par[x];
int z=par[y];
if(z==act)
{
if(lson[y]==x) rotate(x,,lson,rson);
else rotate(x,,lson,rson);
}
else
{
if(lson[z]==y && lson[y]==x)
{
rotate(y,,lson,rson);
rotate(x,,lson,rson);
}
if(rson[z]==y && rson[y]==x)
{
rotate(y,,lson,rson);
rotate(x,,lson,rson);
}
if(rson[z]==y && lson[y]==x)
{
rotate(x,,lson,rson);
rotate(x,,lson,rson);
}
if(lson[z]==y && rson[y]==x)
{
rotate(x,,lson,rson);
rotate(x,,lson,rson);
}
}
}
if(act==-) root=x;
} int find(int val)
{
int now=root;
while(now!=-)
{
if(val==dat[now]) return now;
if(val<dat[now]) now=lson[now];
if(val>dat[now]) now=rson[now];
}
return -;
} void new_node(int val,int p,int &kid)
{
dat[tot]=val;
par[tot]=p;
lson[tot]=-;
rson[tot]=-;
kid=tot;
splay(tot,-);
tot++;
} void insert(int val)
{
siz++;
if(root==-)
{
int temp;
root=tot;
new_node(val,-,temp);
return;
}
int now=root;
while()
{
if(val==dat[now]) return;
if(val<dat[now])
{
if(lson[now]==-)
{
new_node(val,now,lson[now]);
return;
}
else now=lson[now];
}
if(val>dat[now])
{
if(rson[now]==-)
{
new_node(val,now,rson[now]);
return;
}
else now=rson[now];
}
}
} void erase(int x)
{
siz--;
splay(x,-);
if(lson[x]==- && rson[x]==-)
{
root=-;
return;
}
if(lson[x]==-)
{
root=rson[x];
par[rson[x]]=-;
return;
}
if(rson[x]==-)
{
root=lson[x];
par[lson[x]]=-;
return;
}
int pre=lson[root];
while(rson[pre]!=-) pre=rson[pre];
splay(pre,x);
par[pre]=-;
rson[pre]=rson[x];
par[rson[x]]=pre;
root=pre;
} pair<int,int> precursor(int val)
{
int now=root;
int pre=-;
int dif=INF;
while(now!=-)
{
if(dat[now]<val && val-dat[now]<dif)
{
pre=now;
dif=val-dat[now];
}
if(dat[now]>val) now=lson[now];
else now=rson[now];
}
return pair<int,int>(dif,pre);
} pair<int,int> succeed(int val)
{
int now=root;
int suc=-;
int dif=INF;
while(now!=-)
{
if(dat[now]>val && dat[now]-val<dif)
{
suc=now;
dif=dat[now]-val;
}
if(dat[now]>val) now=lson[now];
else now=rson[now];
}
return pair<int,int>(dif,suc);
} int main()
{
cin>>n;
for(int i=;i<n;i++)
{
cin>>a>>b;
if(siz==)
{
insert(b);
type=a;
}
else
{
if(a==type) insert(b);
else
{
pair<int,int> pre=precursor(b);
pair<int,int> suc=succeed(b);
pair<int,int> res=min(pre,suc);
erase(res.second);
ans=(ans+res.first)%MOD;
}
}
}
cout<<ans<<endl;
}
上一篇:【leetcode刷题笔记】Unique Binary Search Trees II


下一篇:BZOJ 1208 [HNOI2004]宠物收养所 | SPlay模板题