题目内容

小美是一个收藏家，他喜欢收集各种珍奇的物品。最近，他在旅游时在俄罗斯购买了一些俄罗斯套娃。他深深地被这些绚丽多彩的小玩意吸引住了，每天都会花费大量的时间玩弄它们。随着时间的推移，他逐渐发现将套娃放在其他套娃内是一个有趣的游戏，并决定挑战自己，看看他是否能以最小的成本套上所有的俄罗斯套娃。

具体的，小美有 $n$ 个俄罗斯套娃，第 $i$ 个俄罗斯套娃的大小为 $a_i$ ，内部空间为 $b_i$ ( $b_i\le a_i$ )和一个价值 $c_i$ 。

题目思路

思路：贪心 + multiset（平衡树）

每个物品中能放至多一个其他的物品，且每个物品只能放在至多一个物品内。

先考虑单位空间价值更大的，让他们内部的空间先被填充。

按照单位空间价值从大到小枚举每个物品，对每个物品找到一个体积小于当前枚举物品的空间的物品。即找到一个小于等于 $x$ 的最大的 $y$ 值。