CF2093E.Min Max MEX

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

子数组被定义为数组中一个或多个连续元素组成的序列。你需要将数组 $a$ 分割成 $k$ 个互不重叠的子数组 $b_1, b_2, \dots, b_k$ ，使得这些子数组的并集等于整个数组。此外，你需要最大化 $x$ 的值，其中 $x$ 等于所有子数组 $b_i$ （ $i \in [1..k]$ ）的 MEX 的最小值。

MEX $(v)$ 表示数组 $v$ 中未出现的最小非负整数。

输入格式

第一行包含一个整数 $t$ （ $1\leq t\leq 10^4$ ）——测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ （ $1\leq k \leq n \leq 2 \cdot 10^5$ ）——数组的长度和需要分割成的子数组数量。

每个测试用例的第二行包含 $n$ 个整数 $a_i$ （ $0\leq a_i\leq 10^9$ ）——数组的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个查询，输出一个数字——最大的 $x$ 值，使得存在一种将数组 $a$ 分割成 $k$ 个子数组的方式，其中所有子数组的 MEX 的最小值等于 $x$ 。

输入输出样例

输入#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

说明/提示

翻译由 DeepSeek V3 完成

输入解题思路，AI测评打分。不知道怎么写?

首页