2093E.md (1536B)
1 Source: https://codeforces.com/problemset/problem/2093/E 2 3 E. Min Max MEX 4 5 time limit per test 6 7 2 seconds 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 $a$ of length $n$ and a number $k$. 22 23 A subarray is defined as a sequence of one or more consecutive elements of the array. You need to split the array $a$ into $k$ non-overlapping subarrays $b_1, b_2, \dots, b_k$ such that the union of these subarrays equals the entire array. Additionally, you need to maximize the value of $x$, which is equal to the minimum MEX$(b_i)$, for $i \in [1..k]$. 24 25 MEX$(v)$ denotes the smallest non-negative integer that is not present in the array $v$. 26 27 Input 28 29 The first line contains an integer $t$ $(1\leq t\leq 10^4)$ — the number of test cases. 30 31 The first line of each test case contains two integers $n$, $k$ $(1\leq k \leq n \leq 2 \cdot 10^5)$ — the length of the array and the number of segments to split the array into. 32 33 The second line of each test case contains $n$ integers $a_i$ $(0\leq a_i\leq 10^9)$ — the elements of the array. 34 35 It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$. 36 37 Output 38 39 For each query, output a single number — the maximum value $x$ such that there exists a partition of the array $a$ into $k$ subarrays where the minimum MEX equals $x$. 40 41 Example 42 43 Input 44 45 ``` 46 7 47 48 1 1 49 50 0 51 52 5 1 53 54 0 1 3 2 4 55 56 6 2 57 58 2 1 0 0 1 2 59 60 5 5 61 62 0 0 0 0 0 63 64 5 2 65 66 2 3 4 5 6 67 68 6 2 69 70 0 0 1 1 2 2 71 72 4 4 73 74 1 0 0 0 75 ``` 76 77 Output 78 79 ``` 80 1 81 5 82 3 83 1 84 0 85 1 86 0 87 ```