Problem Statement

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

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\leq t\leq 10^4)$ — the number of test cases.

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.

The second line of each test case contains $n$ integers $a_i$ $(0\leq a_i\leq 10^9)$ — the elements of the array.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$.

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

Solving

求一个区间的最小MEX值的最大值，考虑二分区间：

二分区间的最小MEX(x)，枚举依靠此MEX值能将数组分为多少个子数组，返回cnt >= k

二分判断函数中利用std::bitset模拟，同时优化空间与时间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

const int N = 2e5+10;
const int M = 0;
//二分求解全局最大最小MEX
//枚举全局最小MEX
int n,k; 
bool check(vector<int>& arr,int x)
{   
    bitset<N> bs;
    bs.reset();
    int cnt = 0;//counts of the subarrays
    int cur_mex = 0;
    for(int i=1;i<=n;i++)
    {   
        if(arr[i]<=n)//剪枝：如果arr[i]>n 其mex一定<=n
        bs[arr[i]] = true;
        while(bs[cur_mex]) cur_mex++;
        if(cur_mex >= x)
        {
            cnt++;
            bs.reset();
            cur_mex = 0;
        }
    }
    bs.reset();
    return cnt >= k;
}
void solve()
{   
    cin >> n >> k;
    vector<int> arr(n+1);
    for(int i=1;i<=n;i++) cin >> arr[i];
    int l = 0,r = 1e9,mid;
    while(l+1<r)
    {
        mid = (l + r) >> 1;
        if(check(arr,mid)) l = mid;
        else r = mid;
    }
    if(check(arr,r))
    {
        l = r;
    }
    cout << l << endl;
}