A16485. Shifted MEX
编程题
普及-
知识点
题目描述
给定一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$。你可以执行下面的操作一次：
- 选择一个整数 $x$（可以为负数），对于每一个 $i$ $(1 \leq i \leq n)$，将 $a_i$ 变为 $a_i + x$。
例如，如果 $a = [1, 3, 4, 2]$，你选择 $x = 3$ 进行操作，则 $a$ 变为 $[4, 6, 7, 5]$。
请输出操作后，数组 $a$ 的 $\operatorname{MEX}(a)^{\ast}$ 的最大可能值。
$\ast$ $\operatorname{MEX}(a)$ 表示数组中未出现的最小非负整数。例如，$\operatorname{MEX}([1, 2, 0, 5]) = 3$，$\operatorname{MEX}([1, 2, 4, 9]) = 0$。
- 选择一个整数 $x$（可以为负数），对于每一个 $i$ $(1 \leq i \leq n)$，将 $a_i$ 变为 $a_i + x$。
例如，如果 $a = [1, 3, 4, 2]$，你选择 $x = 3$ 进行操作，则 $a$ 变为 $[4, 6, 7, 5]$。
请输出操作后，数组 $a$ 的 $\operatorname{MEX}(a)^{\ast}$ 的最大可能值。
$\ast$ $\operatorname{MEX}(a)$ 表示数组中未出现的最小非负整数。例如，$\operatorname{MEX}([1, 2, 0, 5]) = 3$，$\operatorname{MEX}([1, 2, 4, 9]) = 0$。
输入格式
输入的第一行为一个整数 $t$ $(1 \leq t \leq 1000)$，表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ $(1 \le n \le 3000)$，表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(-10^9 \le a_i \le 10^9)$，表示数组 $a$。
保证所有测试用例中 $n$ 之和不超过 $3000$。
每个测试用例的第一行包含一个整数 $n$ $(1 \le n \le 3000)$，表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(-10^9 \le a_i \le 10^9)$，表示数组 $a$。
保证所有测试用例中 $n$ 之和不超过 $3000$。
输出格式
对于每个测试用例，输出执行一次操作后 $\operatorname{MEX}(a)$ 的最大可能值。
输入输出样例
输入 #1
6 1 4 5 0 1 1 2 3 2 1 1 4 4 2 3 6 5 2 4 1 0 -1 6 -1 1 2 3 5 6
输出 #1
1 4 1 3 4 3
说明/提示
对于第一个测试用例，可以选择 $x = -4$，此时 $a = [0]$，$\operatorname{MEX}([0]) = 1$。
对于第二个测试用例，$\operatorname{MEX}$ 已经是 $4$，已是最大值，因此可以选择 $x = 0$ 不进行任何变化。
对于第二个测试用例，$\operatorname{MEX}$ 已经是 $4$，已是最大值，因此可以选择 $x = 0$ 不进行任何变化。