codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.