首页 > 分享 > 【洛谷P2286】宠物收养场【Treap】

【洛谷P2286】宠物收养场【Treap】

萌宠菠菠乐园
2025-01-14 12:38

题目大意：

题目链接：https://www.luogu.org/problem/P2286
一家宠物收养场会陆续到来一些收养人和宠物。每个收养人个宠物都有一个权值kk。如果某个时刻收养人多于宠物，那么新进来一个宠物就会选择权值与自己最接近的收养人，若有两个收养人的权值分别-为k+a,k−ak+a,k-a，那么宠物将选择权值小的收养人。
当收养人少于宠物时，收养人就会选择与自己权值最接近的宠物。
保证任意收养人和宠物的权值不同。定义一次收养的代价为abs(k1−k2)abs(k_1-k_2)，即收养人和宠物的权值差。求代价和。

思路：

显然任意时刻宠物和收养人至少有一个是没有的。如果两者的数量均大于0，那么必然可以不停配对，直到一方数量为0。
所以我们维护两棵平衡树，每一棵维护宠物//收养人的权值。
如果此时进来一只宠物，此时收养人数量大于0，那么就在收养人的平衡树中查找该宠物的权值的前驱后继，然后判断一下和谁配对即可。
如果收养人此时为0，那么就在宠物的平衡树中插入该权值即可。
新增一个收养人的处理方法也是类似的。这样就可以很轻松的解决这道题。

代码：

#include <ctime> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; const int MOD=1000000,Inf=2e9,N=100010; int n,opt,k,root[3],ans; struct treenode {int lc,rc,dat,size,val; }; struct Treap {treenode t[N];int tot=0;int New(int val){t[++tot].val=val;t[tot].dat=rand();t[tot].size=1;return tot;}void update(int x){t[x].size=t[t[x].lc].size+t[t[x].rc].size+1;}void build(int x){root[x]=New(-Inf);t[root[x]].rc=New(Inf);update(root[x]);}void zig(int &x){int y=t[x].lc;t[x].lc=t[y].rc; t[y].rc=x; x=y;update(t[x].rc); update(x);}void zag(int &x){int y=t[x].rc;t[x].rc=t[y].lc; t[y].lc=x; x=y;update(t[x].lc); update(x);}void insert(int &x,int val){if (!x){x=New(val);return;}if (val<t[x].val){insert(t[x].lc,val);if (t[t[x].lc].dat>t[x].dat) zig(x);}else{insert(t[x].rc,val);if (t[t[x].rc].dat>t[x].dat) zag(x);}update(x);}void del(int &x,int val){if (!x) return;if (t[x].val==val){if (t[x].lc || t[x].rc){if (!t[x].lc || t[t[x].lc].dat<t[t[x].rc].dat)zag(x),del(t[x].lc,val);elsezig(x),del(t[x].rc,val);update(x);}else x=0;return;}if (val<t[x].val) del(t[x].lc,val);else del(t[x].rc,val);update(x);}int pre(int x,int val){if (!x) return -Inf;if (t[x].val<val) return max(t[x].val,pre(t[x].rc,val));else return pre(t[x].lc,val);}int next(int x,int val){if (!x) return Inf;if (t[x].val>val) return min(t[x].val,next(t[x].lc,val));else return next(t[x].rc,val);} }Treap1,Treap2; int main() {scanf("%d",&n);srand(time(0));Treap1.build(1); Treap2.build(2);while (n--){scanf("%d%d",&opt,&k);if (opt==0){if (Treap1.t[root[1]].size>2) //Treap中只有-INF和INF两个值时，就相当于没有。{int x=Treap1.pre(root[1],k),y=Treap1.next(root[1],k);if (abs(x-k)<=abs(y-k)){ans=(ans+abs(x-k))%MOD;Treap1.del(root[1],x);}else{ans=(ans+abs(y-k))%MOD;Treap1.del(root[1],y);}}else Treap2.insert(root[2],k);}else{if (Treap2.t[root[2]].size>2){int x=Treap2.pre(root[2],k),y=Treap2.next(root[2],k);if (abs(x-k)<=abs(y-k)){ans=(ans+abs(x-k))%MOD;Treap2.del(root[2],x);}else{ans=(ans+abs(y-k))%MOD;Treap2.del(root[2],y);}}else Treap1.insert(root[1],k);}}printf("%dn",ans);return 0; }