[Mivik Round / 梦境彼岸] [题解] 声海 Sea of Voices

· · 题解

Subtask 1

因为元素都是非负的，我们直接输出最小的两个数即可。

Subtask 2

（真的有人需要吗？）

Subtask 3

（我想了一下，不是很会）

Subtask 4

我们考虑，是什么让我们最小的第三个数不一定是原来的第三个数？是 a_1+a_2！因此我们拓展一下这个思路，每次推算出 a_i 的值后把 S_1,S_2,\dots,S_i（S_k 表示 a 的前 k 项和）从给出的数里面删去（注意重复的数一次只能删一个），于是剩下不相关的数要么就包含 a_{i+1}，要么就包含比 a_{i+1} 更大的数，都是大于 a_{i+1} 的。这时我们再取最小值就是 a_{i+1} 的值了。

这个维护可重数集的插入删除最小值直觉是用 multiset，但想想常数过大应该过不去。于是我们把原来的数集先排好序，然后用一个优先队列从小到大维护删除了的数，每次取数集最小值的时候检查一下就好了。时间复杂度是 O(n^2\log n) 的。显然有不带 \log 的做法，不过作为签到题并没有必要为了微小的复杂度差距增大码量。

ametus.h / code