1875D.md (2129B)
1 Source: https://codeforces.com/problemset/problem/1875/D 2 3 D. Jellyfish and Mex 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array of $n$ nonnegative integers $a_1, a_2, \dots, a_n$. 22 23 Let $m$ be a variable that is initialized to $0$, Jellyfish will perform the following operation $n$ times: 24 25 * select an index $i$ ($1 \leq i \leq |a|$) and delete $a_i$ from $a$. 26 * add $\operatorname{MEX}(a)^{\dagger}$ to $m$. 27 28 Now Jellyfish wants to know the minimum possible final value of $m$ if he performs all the operations optimally. 29 30 $^{\dagger}$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance: 31 32 * The MEX of $[2,2,1]$ is $0$, because $0$ does not belong to the array. 33 * The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not. 34 * The MEX of $[0,3,1,2]$ is $4$ because $0$, $1$, $2$, and $3$ belong to the array, but $4$ does not. 35 36 Input 37 38 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. 39 40 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 5000$) — the size of the array. 41 42 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. 43 44 It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$. 45 46 Output 47 48 For each test case, output a single integer — the minimum value of $m$ if the operations are performed optimally. 49 50 Example 51 52 Input 53 54 ``` 55 4 56 57 8 58 59 5 2 1 0 3 0 4 0 60 61 2 62 63 1 2 64 65 5 66 67 1 0 2 114514 0 68 69 8 70 71 0 1 2 0 1 2 0 3 72 ``` 73 74 Output 75 76 ``` 77 3 78 0 79 2 80 7 81 ``` 82 83 Note 84 85 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$.