自动搬运

查看原文

来自洛谷，原作者为

	Mivik AFO

搬运于2025-08-24 22:36:23，当前版本为作者最后更新于2022-02-03 11:17:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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