题面

题目传送门

思路

根据题意，每一个主人到达收养所后，如果有宠物，就会领养。同样地，宠物也是如此，只要有主人就会被领养。这样就能理解题目中 “宠物收养场总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少”。

如何找到特点值最接近的主人/宠物？找一个集合中最接近 x 的元素，自然就想到了平衡树。我在这道题使用了 Treap。最接近的 x 特征值就是 x 前驱和后继中更接近 x 的那一个。

所以我们可以开两棵 Treap，分别存储宠物的特点值和主人的特点值。再记录下当前两个 Treap 中分别有多少个元素。

每当一个宠物 x 进入，如果主人的 Treap 不为空，就在主人 Treap 中找 x 的前驱和后继，选择更接近 x 的那个（根据题意如果差值相同就选前驱），并累计不满意度总值，然后从主人 Treap 中删除这个元素。否则如果主人的 Treap 为空，就将 x 加入宠物的 Treap 中，等待下一个主人。

对应地，每当一个主人 y 进入，如果宠物的 Treap 不为空，就在宠物 Treap 中找 y 的前驱和后继，选择更接近 y 的那个，然后删除它（已经被领养了），并累计不满意度总值，然后从宠物 Treap 中删除这个元素。否则如果宠物的 Treap 为空，就将 y 加入主人的 Treap 中，等待下一个宠物。

代码

#include<bits/stdc++.h>
using namespace std;
int q;
struct treap{//封装 Treap
	struct node{
		long long x,y,l,r,size,cnt;
	};
	node s[1000001];
	long long top,root;
	void reset(){
		top=0;
		root=0;
	}
	void update(long long x){
		s[x].size=s[s[x].l].size+s[s[x].r].size+s[x].cnt;
	}
	void rotr(long long &x){
		long long l=s[x].l;
		s[x].l=s[l].r;
		s[l].r=x;
		s[l].size=s[x].size;
		update(x);
		x=l;
	}
	void rotl(long long &x){
		long long r=s[x].r;
		s[x].r=s[r].l;
		s[r].l=x;
		s[r].size=s[x].size;
		update(x);
		x=r;
	}
	void add(long long &x,long long data){
		if (!x){
			x=++top;
			s[x].x=data;
			s[x].y=rand()%19260817;
			s[x].cnt=1;
			s[x].size=1;
			s[x].l=0;
			s[x].r=0;
			return;
		}
		s[x].size++;
		if (s[x].x==data){
			s[x].cnt++;
		}else if (data<s[x].x){
			add(s[x].l,data);
			if (s[x].y>s[s[x].l].y){
				rotr(x);
			}
		}else{
			add(s[x].r,data);
			if (s[x].y>s[s[x].r].y){
				rotl(x);
			}
		}
	}
	void del(long long &x,long long data){
		if (s[x].x==data){
			if (s[x].cnt>1){
				s[x].cnt--;
				s[x].size--;
				return;
			}
			if (!s[x].l||!s[x].r){
				x=s[x].l+s[x].r;
				return;
			}
			if (s[s[x].l].y<s[s[x].r].y){
				rotr(x);
				del(x,data);
			}else{
				rotl(x);
				del(x,data);
			}
			return;
		}
		s[x].size--;
		if (data<s[x].x){
			del(s[x].l,data);
		}else{
			del(s[x].r,data);
		}
	}
	long long pre(long long data){
		long long now=root,res=-2147483647;
		while (now){
			if (s[now].x<data){
				res=s[now].x;
				now=s[now].r;
			}else{
				now=s[now].l;
			}
		}
		return res;
	}
	long long nxt(long long data){
		long long now=root,res=2147483647;
		while (now){
			if (s[now].x>data){
				res=s[now].x;
				now=s[now].l;
			}else{
				now=s[now].r;
			}
		}
		return res;
	}
	long long querykth(long long k){
		long long now=root;
		while (now){
			if (s[s[now].l].size<k&&s[s[now].l].size+s[now].cnt>=k){
				return s[now].x;
			}
			if (s[s[now].l].size>=k){
				now=s[now].l;
			}else{
				k-=s[s[now].l].size+s[now].cnt;
				now=s[now].r;
			}
		}
		return 0;
	}
	long long queryrank(long long data){
		long long now=root,res=0;
		while (now){
			if (data==s[now].x){
				return res+s[s[now].l].size+1;
			}
			if (data<s[now].x){
				now=s[now].l;
			}else{
				res+=s[s[now].l].size+s[now].cnt;
				now=s[now].r;
			}
		}
		return res;
	}
};
long long n,ans=0;//ans 为不满意度总和
treap a,b;//存储宠物和主人特征值
long long A=0,B=0;//分别表示宠物和主人 Treap 中有多少个元素
int main(){
	srand(time(0));
	a.reset();
	b.reset();
	cin>>n;
	for (int i=1;i<=n;i++){
		long long x,y;
		cin>>x>>y;
		if (x==0){//如果是宠物
			if (B>0){//如果主人 Treap 不为空（当前有正在等待的主人）
				long long tar1=b.pre(y);//在主人中找前驱
				long long tar2=b.nxt(y);//找后继
				if (y-tar1>tar2-y){//选取更接近的那个
					ans+=tar2-y;//更新不满意度
					b.del(b.root,tar2);//从主人 Treap 中删除匹配到的主人
				}else{
					ans+=y-tar1;//同上
					b.del(b.root,tar1);
				}
				B--;//主人 Treap 元素总和减 1
			}else{//如果没有在等待的主人
				A++;//宠物 Treap 元素总和加 1
				a.add(a.root,y);//宠物 Treap 插入当前宠物的特征值
			}
		}else{
			if (A>0){//同上，只是这次是主人匹配宠物
				long long tar1=a.pre(y);
				long long tar2=a.nxt(y);
				if (y-tar1>tar2-y){
					ans+=tar2-y;
					a.del(a.root,tar2);
				}else{
					ans+=y-tar1;
					a.del(a.root,tar1);
				}
				A--;
			}else{
				B++;
				b.add(b.root,y);
			}
		}
		ans%=1000000;//取模
	}
	cout<<ans%1000000;
}