[ARC121D] 1 or 2 题解

Pretharp · 2023-06-02 18:07:31 · 题解

考虑一次只能吃两颗糖果，显然，在最优的情况下每次会吃掉剩下的糖果中最大的和最小的。然后考虑一次吃一颗糖果的情况，每次吃一颗美味值为 x 的糖果可以看作吃美味值为 x 的糖果以及美味值为 0 的糖果，这样问题又转换为了每次只能吃两颗糖果，至于我们要有多少次只吃一个糖果（也就是向集合里插入多少个 0），可以枚举。注意代码实现的时候应该将 i 个 0 插入在正数和负数的交界处，而非插入在末尾再排序，这样时间复杂度才是 O(n^2) 否则会带 \log（虽然也能过）。