📝 题目大意

给定一个长度为 $N$ 的非负整数序列 $A$，从中选择 $K$ 个元素（保持原顺序），求能得到的子序列 $B$ 的 MEX 的最大值。MEX 定义为最小的不在序列中的非负整数。

💡 解题思路

1. 题目分析：

   • $N \leq 3 \times 10^5$，$A_i \leq 10^9$，数据范围较大，需要 $O(N \log N)$ 或 $O(N)$ 的解法。
   • MEX 只关心集合中有哪些数，与元素顺序无关，因此"保持原顺序"的约束实际上不影响结果。
   • 要让 MEX 尽可能大，需要让 $0, 1, 2, \dots, m-1$ 这 $m$ 个数都出现在 $B$ 中，每个数至少出现一次。由于只能选 $K$ 个元素，所以 $m$ 最大不超过 $K$（每个数至少消耗一个名额）。

2. 算法推导：

   • 先将数组 $A$ 排序（std::sort），方便从小到大遍历。
   • 维护变量 curt 表示当前期望找到的数字（从 $0$ 开始），k 表示剩余可选元素个数，ans 记录答案（初始为 $-1$）。
   • 遍历排序后的数组：
     • 若 k <= 0，说明名额用完了，无法继续扩展 MEX，跳出循环。
     • 若 v[i] != curt，说明数字 curt 在原数组中不存在，MEX 最大只能到 curt，记录答案并跳出。
     • 若 v[i] == curt，说明找到了 curt，消耗一个名额（k--），然后跳过所有等于 curt 的重复元素（while (i < n && v[i] == curt) i++），curt 加一继续找下一个数。
   • 若循环正常结束而 ans 仍为 $-1$，说明所有出现过的连续数字都已被收集，ans = curt。

3. 边界与细节：

   • 当 $K$ 耗尽时，即使后面的数字仍然连续，也无法再选，MEX 止步于当前 curt。
   • 当数组中缺少某个中间数字（如缺少 $2$ 但有 $0,1,3$），MEX 会卡在缺失的数字处，即使 $K$ 还有剩余。
   • 输入中 $A_i$ 可能远大于 $N$，排序后可以直接忽略大于 $K$ 的部分（因为 MEX 最大不超过 $K$），但代码中未做此优化也无妨，因为排序后遍历到 k <= 0 就会 break。
   • 初始 ans = -1 作为哨兵值，用于判断循环是否因找到缺失数字而提前退出。

⏱️ 复杂度分析

• 时间复杂度：$O(N \log N)$，排序占主导，后续遍历为 $O(N)$。
• 空间复杂度：$O(N)$，存储输入数组。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;
int n, k;
int main() {
  scanf("%d%d", &n, &k);
  std::vector<int> v(n, 0);
  for (int i = 0; i < n; i++) {
    scanf("%d", &v[i]);
  }
  // 排序后从小到大处理，方便按顺序查找 0, 1, 2, ...
  std::sort(v.begin(), v.end());
  int curt = 0;      // 当前期望找到的数字
  int i = 0;         // 遍历指针
  int ans = -1;      // 哨兵：-1 表示尚未找到缺失数字
  for (; i < n && ans == -1;) {
    if (k <= 0) { break; }           // 名额用完，无法继续扩展 MEX
    if (v[i] != curt) {              // 数字 curt 在原数组中不存在
      ans = curt;                    // MEX 最大为 curt
      break;
    }
    k--;                             // 消耗一个名额选取 curt
    while (i < n && v[i] == curt) {  // 跳过所有重复的 curt
      i++;
    }
    curt++;                          // 尝试找下一个数
  }
  if (ans == -1) ans = curt;         // 所有连续数字都找到了，MEX = curt
  printf("%d", ans);
  return 0;
}