先来看一道题。
link.
我们发现很不好搞的一件事情就是有两个东西需要我们去考虑,如果两个都枚举肯定会炸,所以我们用到一个小 trick。
我们想办法只去考虑一个东西,我们可以利用排序。
具体的,我们可以将盒子和巧克力放在一起,按照横长降序排序,我们每次枚举到一个盒子,就把它放进一个 multiset 里面,当我们枚举到一个巧克力的时候,我们 multiset 里面已有的盒子肯定在横向上比它长,所以我们只需要在这些之中查找纵向上比它也长的就可以找到满足条件的盒子了,再搭配贪心即可通过本题。
another.
我们如何在枚举 \(t\) 的时候如何快速找到最小的 \(b\) 呢?肯定不能线段树因为这些歌曲在序列上不一定连续,所以我们将所有的按 \(b\) 降序排序,并放进一个 priority_queue 里面。
那么当我们当前这个结点入队的时候,它的 \(b\) 一定是所有已经入队的结点中的最小值,那么我们只需要用 priority_queue 查找出 \(k\) 个 \(t\) 最长的歌曲(必须包括当前这个),求出这些 \(t\) 的和,再乘上它的 \(b\),最后对所有的取最小值即可。
与之类似的还有这道题。
两两枚举显然不行,那么如何快速的知道两者中 \(v\) 的较大值呢?
类似,我们将原来的奶牛按照 \(v\) 降序排序,这样我们每次枚举到一头牛,它前面的已经考虑过的牛的 \(v\) 显然比他大,那么我们只需要知道前面枚举的牛距它的距离和即可。
我们显然可以按坐标插入牛,用线段树维护。