思路分析

我们的目标是最大化 $\sum \operatorname{vac}(i)$。由于 $\operatorname{vac}(i)$ 的定义依赖于前缀空缺数，并且 $\operatorname{vac}(i)$ 序列是非递减的（$\operatorname{vac}(1) \le \operatorname{vac}(2) \le \dots \le \operatorname{vac}(n)$），我们希望让 $\operatorname{vac}(i)$ 的值尽可能早地、尽可能大地增长。

$\operatorname{vac}(i)$ 的值等于集合 $\{x_1, \dots, x_i\}$ 中未出现的最小非负整数。为了让 $\operatorname{vac}(i)$ 的值变大，我们需要让前缀 $\{x_1, \dots, x_i\}$ 尽可能地包含从 $0$ 开始的连续整数。

• 为了最大化 $\operatorname{vac}(1)$，我们应该选择 $x_1=0$（如果给定的元素中有 $0$ 的话）。这样 $\operatorname{vac}(1)=1$。如果选择其他数，$\operatorname{vac}(1)=0$。
• 为了最大化 $\operatorname{vac}(2)$，在 $x_1=0$ 的基础上，我们应该选择 $x_2=1$（如果给定的元素中有 $1$ 的话）。这样 $\{x_1, x_2\} = \{0, 1\}$，使得 $\operatorname{vac}(2)=2$。
• 以此类推，为了让 $\operatorname{vac}(i)$ 达到最大可能值 $i$，我们需要让前缀 $\{x_1, \dots, x_i\}$ 恰好是 $\{0, 1, \dots, i-1\}$。