洛谷 P2286 & LOJ 10144 -「一本通 4.6 练习 1」宠物收养所

题面

题目传送门

思路

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

如何找到特点值最接近的主人/宠物?找一个集合中最接近 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 中,等待下一个宠物。

代码

暂无评论

发送评论


				
上一篇
下一篇