[ABC314G] Amulets
考虑如果 \(k\) 是固定的,可以二分答案,然后暴力 check
。
而本题显然不行。
有一个简单的性质:如果我们知道了最多可以打几只怪兽,那么带某种护身符的贡献是一定的,此时可以直接计算。
由于 \(k\) 递增时,答案也一定递增。
我们可以考虑使用一个指针表示当前能够打的怪数量(为了方便,我们假定指针所指的前一个位置恰好是能打的最后一只),然后用一个数据结构维护前 \(k\) 大的值,用当前怪的攻击力总和减去,看体力够不够,如果够了指针往右移。
这个数据结构就是我们维护第 \(k\) 大时用的对顶堆。
考虑如果上堆的数更新,答案也要更新。
如果下堆的数比上堆大了,就换上去。
还要支持堆中元素的修改。
手写堆可以实现增加值的操作,但是下面的堆是大根堆,上面的是小根堆,并不适用。
如果要实现这个操作,只能开另外一个堆来表示临时删除,下次取堆顶就比较两堆。
这样一共四个堆,十分麻烦。
由于 multiset
支持修改数(找到、删除、插入新值),用其可以方便许多。复杂度还是 \(O(n\log n)\)。
注意 long long
。(尽管血量并不会超,但是为了方便处理集合中的使用护身符的值)