我们的目标是最大化 $\sum b_i$ 。由于 $b_i$ 的定义依赖于前缀 $MEX$ ，并且 $b_i$ 序列是非递减的（ $b_1 \le b_2 \le ... \le b_n$ ），我们希望让 $b_i$ 的值尽可能早地、尽可能大地增长。

$b_i = MEX(\{a_1, ..., a_i\})$ 。为了让 $b_i$ 的值变大，我们需要让前缀 $\{a_1, ..., a_i\}$ 尽可能地包含从 $0$ 开始的连续整数。

为了最大化 $b_1 = MEX(\{a_1\})$ ，我们应该选择 $a_1=0$ （如果数组 $a$ 中有 $0$ 的话）。这样 $b_1=1$ 。如果选择其他数， $b_1=0$ 。
为了最大化 $b_2 = MEX(\{a_1, a_2\})$ ，在 $a_1=0$ 的基础上，我们应该选择 $a_2=1$ （如果数组 $a$ 中有 $1$ 的话）。这样 $\{a_1, a_2\} = \{0, 1\}$ ，使得 $b_2=2$ 。
以此类推，为了让 $b_i$ 达到最大可能值 $i$ ，我们需要让前缀 $\{a_1, ..., a_i\}$ 恰好是 $\{0, 1, ..., i-1\}$ 。

P3583.第2题-小美的mex之和

1000ms

Difficulty: 4

所属公司 : 美团

算法与标签>贪心算法

题目内容

小美有一个长度为 $n$ 的数组 $a$ 。你可以将 $a$ 任意重排。定义一个长度为 $n$ 的数组 $b$ ，其中 $b_i= MEX(a_1,a_2,...,a_i$ )。你需要最大化数组 $b$ 中的元素之和。

你需要输出最大的元素和，以及一个可能的 $a$ 的重排方案。

【名词解释】

$MEX$ ：整数数组的 $MEX$ 定义为没有出现在数组中的最小非负整数。例如 $MEX$ { $1,2,3$ } $=0、MEX$ { $0,2,5$ } $=1$ 。

第一行输入一个整数 $n(1≦n≦2·10^5)$ ，表示数组 $a$ 的长度

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(0≦a_i≦10^9)$ ，表示数组 $a$ 的元素。

第一行输出一个整数，表示 $b$ 的元素和。

第二行输出 $n$ 个整数，表示重排后的 $a$ 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查等案正确性。

输入

3
1 0 1

输出

5
0 1 1

说明

将 $a$ 重排为 { $0,1,1$ } 后，数组 $b$ 为 { $1,2,2$ } ，元素和为 $5$ 。

可以证明不存在一个重排使得数组 $b$ 的元素和大于 $5$ 。

输入

6
0 1 2 3 4 5

输出

21
0 1 2 3 4 5

输入

预期输出（选填）