310717: CF1875D. Jellyfish and Mex
Description
You are given an array of $n$ nonnegative integers $a_1, a_2, \dots, a_n$.
Let $m$ be a variable that is initialized to $0$, Jellyfish will perform the following operation $n$ times:
- select an index $i$ ($1 \leq i \leq |a|$) and delete $a_i$ from $a$.
- add $\operatorname{MEX}(a)^{\dagger}$ to $m$.
Now Jellyfish wants to know the minimum possible final value of $m$ if he performs all the operations optimally.
$^{\dagger}$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:
- The MEX of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
- The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
- The MEX of $[0,3,1,2]$ is $4$ because $0$, $1$, $2$, and $3$ belong to the array, but $4$ does not.
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 5000$). The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \leq n \leq 5000$) — the size of the array.
The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq 10^9$) — the integers in the array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.
OutputFor each test case, output a single integer — the minimum value of $m$ if the operations are performed optimally.
ExampleInput4 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 3Output
3 0 2 7Note
In the first test case, we delete elements from $a$ in the following order: $[5,2,\color{red}{1},0,3,0,4,0] \to [5,2,0,3,\color{red}{0},4,0] \to [5,2,\color{red}{0},3,4,0] \to [5,2,3,4,\color{red}{0}] \to [5,2,\color{red}{3},4] \to [\color{red}{5},2,4] \to [\color{red}{2},4] \to [\color{red}{4}] \to [~]$. The value of $m$ will be $1+1+1+0+0+0+0+0=3$.
Output
你有一个由非负整数组成的数组a[1], a[2], ..., a[n]。变量m初始化为0，水母将会执行以下操作n次：
1. 选择一个索引i（1≤i≤|a|）并从a中删除a[i]。
2. 将MEX(a)添加到m中。
现在水母想知道如果它执行所有操作最优化的情况下，m的最小可能最终值是多少。
MEX（最小排除）数组的定义是数组中不存在的最小非负整数。例如：
- 数组[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≤t≤5000）。接下来是每个测试案例的描述。
每个测试案例的第一行包含一个整数n（1≤n≤5000）——数组的大小。
每个测试案例的第二行包含n个整数a[1], a[2], ..., a[n]（0≤a[i]≤10^9）——数组中的整数。
保证所有测试案例的n之和不超过5000。
输出数据格式：
对于每个测试案例，输出一个整数——如果操作最优化的情况下m的最小值。
示例输入输出：
输入：
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
注意：
在第一个测试案例中，我们按照以下顺序从a中删除元素：[5,2,1,0,3,0,4,0] → [5,2,0,3,0,4,0] → [5,2,0,3,4,0] → [5,2,3,4,0] → [5,2,3,4] → [5,2,4] → [2,4] → [4] → [~]。m的值将是1+1+1+0+0+0+0+0=3。题目大意： 你有一个由非负整数组成的数组a[1], a[2], ..., a[n]。变量m初始化为0，水母将会执行以下操作n次： 1. 选择一个索引i（1≤i≤|a|）并从a中删除a[i]。 2. 将MEX(a)添加到m中。 现在水母想知道如果它执行所有操作最优化的情况下，m的最小可能最终值是多少。 MEX（最小排除）数组的定义是数组中不存在的最小非负整数。例如： - 数组[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≤t≤5000）。接下来是每个测试案例的描述。 每个测试案例的第一行包含一个整数n（1≤n≤5000）——数组的大小。 每个测试案例的第二行包含n个整数a[1], a[2], ..., a[n]（0≤a[i]≤10^9）——数组中的整数。 保证所有测试案例的n之和不超过5000。 输出数据格式： 对于每个测试案例，输出一个整数——如果操作最优化的情况下m的最小值。 示例输入输出： 输入： 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 注意： 在第一个测试案例中，我们按照以下顺序从a中删除元素：[5,2,1,0,3,0,4,0] → [5,2,0,3,0,4,0] → [5,2,0,3,4,0] → [5,2,3,4,0] → [5,2,3,4] → [5,2,4] → [2,4] → [4] → [~]。m的值将是1+1+1+0+0+0+0+0=3。