CF2055E Haystacks
Cute_Fish
·
·
题解
贪心好题/bx。
先判断是否有解，考虑枚举一个 i 把其他草垛都清空然后扔到 i 上，最后再考虑清空 i，那么有解的充要条件即 \sum a_i\le \sum b_i -\min b_i。进一步，我们的答案上界为 2\sum a_i 下界为 \sum a_i。
考虑钦定草垛清空顺序为 1\sim n 怎么做。贪心地想，每个草垛的草要尽量往前面已经清空的草垛扔，但有些就必须要扔到还未清空的草垛上导致我们无法取到下界。若当前考虑到 i，则必须要放到其他未清空草垛上的数量为 c_i=\max(0,\sum_{j=1}^i a_j-\sum_{j=1}^{i-1}b_j)。答案显然是 \sum a_i+\max c_i。问题转为求一组最优的顺序。
+ 对于 $a_i\le b_i$ 这一类，只需要保证 $a_x\ge a_y$，直接按 $a$ 升序排序。
+ 对于 $a_i>b_i$ 这一类，同理也只需要保证 $b_x\le b_y$，那么直接按 $b$ 降序排序。
但是到这还没结束，你发现还有隐含条件即 $c_n=0$，也就是保证最后没有多的。把式子写出来有 $\sum b_j-a_j\ge b_n$，不妨枚举最后一个草垛是哪个，先排好序预处理出前缀 $\max$ 和后缀 $\max$，由于扣掉单点放到后面相当于后缀减，容易 $O(1)$ 维护变化后的 $\max c_i$，于是就做完了，时间复杂度 $O(n\log n)$。