洛谷 CF1875D · 难度 普及+/提高

题目描述

给定一个包含 $n$ 个非负整数的数组 $a_1,a_2,\dots ,a_n$。

令 $m$ 为一个初始值为 $0$ 的变量，Jellyfish 将进行如下操作共 $n$ 次：

• 选择一个下标 $i$（$1\le i\le |a|$），并从 $a$ 中删除 $a_i$。
• 将 $\mathrm{MEX}(a{)}^{†}$ 加到 $m$ 上。

现在，Jellyfish 想知道，如果每一步都最优地进行操作，$m$ 的最终最小可能值是多少。

${}^{†}$ 数组的 MEX（minimum excluded）是指不属于该数组的最小非负整数。例如：

• $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 不在数组中。
• $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 在数组中，但 $2$ 不在。
• $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$、$3$ 都在数组中，但 $4$ 不在。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1\le t\le 5000$），表示测试用例的数量。

每组测试用例的第一行包含一个整数 $n$（$1\le n\le 5000$），表示数组的大小。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$（$0\le a_i\le {10}^9$），表示数组中的元素。

保证所有测试用例中 $n$ 的总和不超过 $5000$。

输出格式

对于每组测试用例，输出一个整数，表示在最优操作下 $m$ 的最小值。

说明/提示

在第一个测试用例中，可以按如下顺序删除 $a$ 中的元素：$[5,2,1,0,3,0,4,0]\to [5,2,0,3,0,4,0]\to [5,2,0,3,4,0]\to [5,2,3,4,0]\to [5,2,3,4]\to [5,2,4]\to [2,4]\to [4]\to []$。$m$ 的值为 $1+1+1+0+0+0+0+0=3$。

由 ChatGPT 4.1 翻译

样例

样例 1

输入

4
8
5 2 1 0 3 0 4 0
2
1 2
5
1 0 2 114514 0
8
0 1 2 0 1 2 0 3

输出

3
0
2
7