Codeforces Round 1016 (Div. 3):2093E - Min Max MEX

2093E - Min Max MEX

题目：https://codeforces.com/contest/2093/problem/E
E. Min Max MEX

time limit per test ：2 seconds
memory limit per test ：256  megabytes
You are given an array a of length n and a number k.
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 b1,b2,…,bk
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(bi)
, for i∈[1..k] MEX(v) denotes the smallest non-negative integer that is not present in the array v
.

Input
The first line contains an integer t
(1≤t≤104)    — the number of test cases.
The first line of each test case contains two integers n， k  (1 ≤ k ≤ n ≤ 2⋅105)
— the length of the array and the number of segments to > split the array into. The second line of each test case contains n integers ai (0≤ai≤109)
— the elements of the array.
It is guaranteed that the sum of n
across all test cases does not exceed 2e5

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

让我们说中文：
给你一个长度为 n 的数组 a 和一个整数 k。
我们定义 子数组 为数组中一段连续的元素序列。
你需要将整个数组 a 分成 k 个互不重叠的子数组 b₁, b₂, ..., bₖ，使得这些子数组的并集恰好等于整个数组 a。
此外，你需要最大化一个值 x，这个值是所有子数组中 MEX(bᵢ) 的最小值
即：x = min(MEX(b₁), MEX(b₂), ..., MEX(bₖ))


来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！