题目描述

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。

你需要将数组 $a$ 分割成 $k$ 个非空且不重叠的连续子数组 $b_1, b_2, \dots, b_k$，使得这些子数组的并集恰好是整个数组 $a$。

你需要找到一种分割方案，使得所有子数组 $b_i$ 的 MEX 值的最小值尽可能大。输出这个最大的最小值。

MEX$(v)$ 指的是数组（或集合） $v$ 中未出现的最小非负整数。例如：
MEX$([0, 1, 3]) = 2$
MEX$([1, 2, 3]) = 0$
* MEX$([0, 1, 2]) = 3$

样例

输入 #1:
7
1 1
0
5 1
0 1 3 2 4
6 2
2 1 0 0 1 2
5 5
0 0 0 0 0
5 2
2 3 4 5 6
6 2
0 0 1 1 2 2
4 4
1 0 0 0

输出 #1:
1
5
3
1
0
1
0

样例 1 解释 (第 3 个测试用例):
n=6, k=2, a = [2, 1, 0, 0, 1, 2]
一种分割方案是: b₁ = [2, 1, 0], b₂ = [0, 1, 2]
MEX(b₁) = MEX([2, 1, 0]) = 3 (包含 0, 1, 2)
MEX(b₂) = MEX([0, 1, 2]) = 3 (包含 0, 1, 2)
该方案的最小 MEX 是 min(3, 3) = 3。
可以证明，无法找到一种分割方案使得最小 MEX 大于 3。因此答案是 3。

算法 (二分答案 + 贪心)

$O(n \log n)$

思路分析

1. 问题目标: 我们要最大化分割后所有子数组 MEX 的最小值。设这个最大的最小值为 $X$。

2. 二分答案的适用性 (单调性):
   考虑目标值 $X$。如果我们能够找到一种分割方案，使得所有子数组的 MEX 都 $\ge X$，那么是否也能找到一种方案使得所有子数组的 MEX 都 $\ge X-1$ 呢？
   答案是肯定的。如果一个子数组的 MEX $\ge X$，那么它必然包含了 $0, 1, \dots, X-1$ 这些数。既然它包含了 $0, \dots, X-1$，那它也一定包含了 $0, 1, \dots, (X-1)-1$。所以，它的 MEX 也必然 $\ge X-1$。
   因此，如果目标值 $X$ 是可行的（存在一种分割使得最小 MEX $\ge X$），那么所有小于 $X$ 的值 $X’$ 也一定是可行的。
   反之，如果目标值 $X$ 是不可行的，那么所有大于 $X$ 的值 $X’$ 也一定是不可行的。
   这种单调性表明我们可以使用 二分查找 来寻找最大的可行 $X$。

3. 二分查找的范围:
   MEX 的最小值是 0（例如，如果某个子数组不包含 0）。
   MEX 的最大可能值是多少？如果一个子数组包含了 $0, 1, \dots, n-1$，那么它的 MEX 就是 $n$。如果它包含了 $0, 1, \dots, n$，它的 MEX 就是 $n+1$。所以，MEX 的值可能在 $[0, n+1]$ 范围内。一个安全的二分上界可以是 $n$ 或 $n+1$。代码中使用了 $[0, n]$ 作为二分范围。

4. check(x) 函数:
   二分查找的核心是实现一个 check(x) 函数，该函数判断：是否存在一种将数组 $a$ 分割成 至少 $k$ 个子数组的方案，使得每个子数组的 MEX 都 $\ge x$？

   • 为什么是“至少 k 个”？ 如果我们能将数组分割成 $k’ > k$ 个满足条件的子数组，我们可以通过合并相邻的子数组来减少子数组的数量，最终得到恰好 $k$ 个子数组。合并后的子数组包含原来两个子数组的所有元素，如果原来两个子数组的 MEX 都 $\ge x$，合并后的子数组也必然包含 $0, 1, \dots, x-1$，所以其 MEX 也 $\ge x$。因此，检查能否分成 至少 $k$ 个是等价且更方便的。
   • MEX $\ge x$ 的条件: 一个子数组 $b$ 的 MEX $\ge x$ 当且仅当该子数组包含了所有非负整数 $0, 1, 2, \dots, x-1$。
   • 贪心策略: 为了尽可能多地分割出满足条件的子数组，我们应该让每个子数组尽可能短。我们从左到右扫描原数组 $a$，尝试构建第一个满足 MEX $\ge x$ 的子数组。一旦找到了这样一个最短的前缀子数组，我们就将其作为一个分割出的块，然后从下一个位置开始，继续寻找下一个满足条件的最短子数组。
   • 实现 check(x):
     1. 如果 $x=0$，任何非空子数组的 MEX 都 $\ge 0$，所以一定可行，直接返回 true。（虽然代码中没有显式处理，但在逻辑上是正确的，因为 x=0 时 vis 数组大小为 0，cur == x 立刻成立）。
     2. 使用一个布尔数组 vis (大小为 $x$) 来标记当前正在构建的子数组中是否已经出现了数字 $0, 1, \dots, x-1$。
     3. 使用一个计数器 cur 记录当前子数组中已经找到的不同数字（范围在 $[0, x-1]$ 内）的数量。
     4. 使用一个计数器 cnt 记录已经成功分割出的满足条件的子数组数量。
     5. 遍历数组 $a$ 的每个元素 a[i]：
        • 如果 a[i] 在范围 $[0, x-1]$ 内，并且在当前子数组中还未出现过 (!vis[a[i]])：
          • 标记 vis[a[i]] = true。
          • cur++。
        • 当 cur == x 时，表示当前子数组已经包含了 $0, \dots, x-1$ 所有数字。我们成功找到了一个满足条件的子数组。
          • cnt++。
          • 重置 cur = 0。
          • 重置 vis 数组（所有元素设为 false），为构建下一个子数组做准备。
     6. 遍历结束后，如果 cnt >= k，则说明存在一种分割方案满足条件，返回 true。否则返回 false。

5. 二分查找实现:

   • 设置二分查找的下界 lo = 0，上界 hi = n。
   • 循环进行直到 lo == hi。
   • 计算中间值 mid = lo + (hi - lo + 1) / 2 (这种写法向上取整，配合 lo = mid 和 hi = mid - 1 的更新方式，是查找最大可行值的常用模板)。
   • 调用 check(mid)：
     • 如果 check(mid) 返回 true，说明 mid 是一个可能的答案，或者答案可能更大。更新下界 lo = mid。
     • 如果 check(mid) 返回 false，说明 mid 太大了，答案一定比 mid 小。更新上界 hi = mid - 1。
   • 循环结束后，lo (或 hi) 就是最大的满足 check(x) 为 true 的 $x$，即为所求答案。

时间复杂度

• check(x) 函数：遍历数组 $a$ 一次，时间复杂度为 $O(n)$。内部对 vis 数组的操作（访问、fill）总共也是 $O(n)$ 级别（因为 fill 的总调用次数与 cnt 相关，而 cnt * x 不会超过 n 太多）。所以 check(x) 的复杂度是 $O(n)$。
• 二分查找：执行 $\log n$ 次 check 函数调用。
• 总时间复杂度：$O(n \log n)$。

空间复杂度

• check(x) 函数中使用了一个大小为 $x$ 的 vis 数组。由于 $x \le n$，空间复杂度为 $O(n)$。
• 总空间复杂度：$O(n)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

// 定义常用类型别名
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

// 处理单个测试用例的函数
void solve() {
    int n, k; // 数组长度 n, 需要分割的子数组数量 k
    std::cin >> n >> k;

    std::vector<int> a(n); // 存储输入的数组 a
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    // check(x) 函数：判断是否能将数组 a 分割成至少 k 个子数组，
    // 使得每个子数组的 MEX 值都 >= x
    auto check = [&](int x) {
        // vis[j] = true 表示数字 j (0 <= j < x) 在当前子数组中已出现
        std::vector<bool> vis(x); 
        int cnt = 0; // 记录成功分割出的满足条件的子数组数量
        int cur = 0; // 记录当前子数组中已出现的不同数字 (0..x-1) 的数量

        // 从左到右遍历数组 a
        for (int i = 0; i < n; i++) {
            // 如果当前元素 a[i] 在目标范围 [0, x-1] 内，
            // 并且在当前子数组中尚未出现过
            if (a[i] < x && !vis[a[i]]) {
                vis[a[i]] = true; // 标记为已出现
                cur++;            // 增加计数
            }
            // 如果当前子数组已包含 0 到 x-1 所有数字
            if (cur == x) {
                cur = 0; // 重置计数器，开始下一个子数组
                // 重置 vis 数组，为下一个子数组做准备
                std::fill(vis.begin(), vis.end(), false); 
                cnt++; // 成功分割出一个子数组，增加总数
            }
        }
        // 判断成功分割的子数组数量是否 >= k
        return cnt >= k;
    };

    // 二分查找最大的可行 x
    int lo = 0, hi = n; // 二分范围 [0, n] (包含 n 是安全的上界)
    while (lo < hi) {
        // 计算中间值 x，向上取整
        // 这种写法等价于 ceil((lo + hi) / 2.0)
        int x = (lo + hi + 1) / 2; 
        if (check(x)) {
            // 如果 x 可行，说明答案可能是 x 或者更大
            // 移动下界 lo 到 x
            lo = x;
        } else {
            // 如果 x 不可行，说明答案必须小于 x
            // 移动上界 hi 到 x - 1
            hi = x - 1;
        }
    }
    // 循环结束时，lo == hi，即为最大的可行 x
    std::cout << lo << "\n";
}

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    std::ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    std::cin.tie(nullptr);

    int t; // 测试用例数量
    std::cin >> t;

    // 处理每个测试用例
    while (t--) {
        solve();
    }

    return 0; // 程序正常结束
}