首先看到最大值最小就想到二分答案
当我们二分了一个\(x\)，我们考虑到恰好等于\(k\)的宣发不太好选，不如直接取得越多越好，换言之枚举分界点，看前后缀在选的数之和\(\leq x\)的情况下最多能选多少个，再合并
而选数的过程可以用堆来维护前缀没有被选到数的最小值
最终复杂度\(O(n\log n\log A)\)
能通过本题，但两个\(\log\)的复杂度不够优秀，我们考虑优化复杂度
首先二分是不太好去掉的，所以我们考虑能不能把堆给优化掉
我们考虑换一种方法来维护堆，我们不维护没选过的数，而考虑维护选过数的最大值
当一个新的数进来后，我们观察能否这个数把最大值替换掉
这时可以发现我们的操作变成了：
-
插入一个数
-
弹出一个最大值并删除
我们发现我们计算了\(\log A\)轮答案中每轮加入的数的顺序都是不变的，因此我们不妨对每个\(a_i\)预处理出他加入后会到哪个元素前面(即找到最大的\(a_j\)(注意不是\(j\))满足\(j < i\)且$a_j \leq a_i)，然后用链表维护本题即可
但这样其实有一个问题，就是如果\(a_j\)被删除了怎么办
我们发现如果\(a_j\)都被删除了\(a_i\)被加入后肯定也会不满足条件而接着删除，否则我们取\(a_j\)一定是比\(a_i\)更优的
因此如果找不到\(a_j\)不妨直接不加入\(a_i\)即可
最终复杂度\(O(n\log A)\)
标签：log,删除,复杂度,最大值,CF1837F,维护,我们 From： https://www.cnblogs.com/fox-konata/p/17655272.html