题面 APIO2012 派遣 Solution 这是一道左偏树的模板题,不会左偏树的可以戳这里 显然,我们可以发现对于同一颗子树,我们想让取的人尽可能便宜,如果说目前为止取的价格超过$C$,就优先把贵的人先丢掉。 因此,我们考虑用左偏树来维护这个东西。对于每一个人,我们都建一颗以价格为关键字的大根堆。考虑从下往上合并,一旦堆的元素总和超过$C$就不断弹栈,弹到合法为止。然后我们算一下$l_i*sum$,取个最大值就好。 时间复杂度$O(nlogn)$ 就酱,我们就可以把这道题切掉啦(ノ゚∀゚)ノ Code //Lu…