U725151 the cure

:::info[Solution] 因为之前是出给基础赛的所以写得比较详细。 首先需要特判掉 $n = 1$ 的情况，此时无法进行任何操作，答案为 $S_1$。 容易发现，为了通过操作获得一个 $x$，最优的操作是选择 $T = \{0, 1, \dots, x - 1\}$，因为如果有多余的元素显然可以去掉。 发现直接贪心没有正确性或难以实现。注意到答案（在 $n \gt 1$ 时）有单调性，因此考虑二分。考虑怎么判定，发现想要凑出 $x$，我们需要 $0$ 到 $x - 1$ 各一个；于是我们又可以考虑怎么凑出一个 $x - 1$；依次类推，发现最后的限制是至少需要多少个 $0$，于是我们只需要在过程中统计 $0$ 的数量即可。 设 $c_j$ 表示 $j$ 的数量。具体地，设当前考虑了 $i$，有 $s$ 个 $0$，需要 $0$ 到 $i - 1$ 各 $r$ 个。 - 初始时 $i = x$；对 $\ge x$ 的每个数操作一次变为 $0$，因此有 $s = c_0 + \sum_{j = x}^n c_j$ 个 $0$；需要 $0$ 到 $x - 1$ 各一个，因此 $r = 1$。 - 从 $x - 1$ 到 $1$ 依次枚举 $i$。 - 若 $c_i \ge r$，那么可以将多余的 $c_i - r$ 个 $i$ 各操作一次变为 $0$，因此令 $s' \leftarrow s + c_i - r$。 - 若 $c_i \lt r$，那么还需要额外的 $r - c_i$ 个 $i$，将这一部分转化为 $0$ 到 $i - 1$ 各 $r - c_i$ 个，因此令 $r' \leftarrow r + r - c_i$。 最终，若 $s \ge r$ 那么答案 $x$ 合法，否则不合法。注意过程中 $r$ 是 $O(2^n)$ 的，所以当 $r \gt n$ 时可以直接判定为不合法。注意到答案的上界是 $n$，因此可以将 $\ge n$ 的数直接变为 $0$。 时间复杂度 $O(n \log n)$。 ```cpp int n, s, cnt[1000005]; bool chk(int x) { int sum = cnt[0], req = 1; rep(i, x, n) sum += cnt[i]; _rep(i, x - 1, 1) { if(cnt[i] < req) req += req - cnt[i]; else sum += cnt[i] - req; if(req > n) return 0; } return sum >= req; } void solve() { cin >> n; rep(i, 0, n) cnt[i] = 0; rep(i, 1, n) cin >> s, ++cnt[s > n ? 0 : s]; if(n == 1) return cout

给定一个大小为 $n$ 的可重集 $S$。你可以进行若干次（包括 $0$ 次）如下操作，直至集合的大小变为 $1$： - 选择 $S$ 的一个非空子集 $T$，从 $S$ 中移除 $T$ 的所有元素，并将 $\operatorname{mex}(T)$ 加入到 $S$ 中。形式化地：$S \leftarrow (S \setminus T) \cup \{\operatorname{mex}(T)\}$，其中 $\operatorname{mex}(T)$ 定义为集合 $T$ 中未出现的最小非负整数。 你的目标是使操作结束时集合中仅剩的元素 $x$ 最大化。请输出 $x$ 的最大值。 请注意，当集合大小为 $1$ 时你不能再进行任何操作。

**本题单个测试点内有多组测试数据。** 第一行，包含一个整数 $T$，表示测试数据的组数。 对于每组数据： - 第一行，包含一个正整数 $n$，表示可重集 $S$ 的大小。 - 第二行，包含 $n$ 个非负整数，表示可重集 $S$ 的元素 $S_1, S_2, \dots, S_n$。

$T$ 行，每行一个非负整数，表示操作结束时集合中仅剩的数 $x$ 的最大值。

**【样例 #1 解释】** 对于第一组测试数据，一种最优的操作序列如下： - 选择 $T = \{0\}$，操作后 $S = \{0, 1\}$。 - 选择 $T = \{0, 1\}$，操作后 $S = \{2\}$ - 此时集合大小为 $1$，$x = 2$，停止操作。 可以证明，不存在操作序列使得答案大于 $2$。 对于第二组测试数据，一种可能的操作序列如下： - 选择 $T = \{2, 4\}$，$S$ 变为 $\{0, 0, 1\}$。 - 选择 $T = \{0, 0, 1\}$，$S$ 变为 $\{2\}$。 - 此时集合大小为 $1$，$x = 2$，停止操作。 可以证明，不存在操作序列使得答案大于 $3$。 **【数据范围】** 设 $\sum n$ 表示单个测试点中每组数据的 $n$ 之和。 ::cute-table{tuack} | 子任务 | $\sum n$ | 特殊性质 | 依赖 | 分值 | | :----: | :--------: | :--------------------------------: | :--------: | :--: | | $1$ | $\le 10$ | 无 | 无 | $10$ | | $2$ | $\le 100$ | ^ | $1$ | $15$ | | $3$ | $\le 1000$ | ^ | $2$ | $15$ | | $4$ | $\le 10^6$ | $S$ 中 $0$ 到 $n - 1$ 各出现了一次 | 无 | $10$ | | $5$ | ^ | $S_i = 0$ | ^ | $15$ | | $6$ | ^ | $S_i \le 10$ | $5$ | $15$ | | $7$ | ^ | 无 | $1 \sim 6$ | $20$ | 对于所有数据，保证： - $1 \le T \le 10^6$。 - $1 \le n, \sum n \le 10^6$。 - $\forall i \in [1, n], 0 \le S_i \le 10^9$。