Hello 2026——B. Yet Another MEX Problem（由鸽巢原理导出决策根本无关紧要）

题目大意

问题描述

给定长度为 n 的数组 a 和整数 k。需要执行 n−k+1 次操作:

• 每次操作选择一个长度为 k 的窗口,该窗口的 MEX 值在所有大小为 k 的窗口中最大

• 从这个窗口中删除任意一个元素

• 重复以上过程直到数组长度变为 k−1

目标: 最大化最终剩余元素的 MEX 值

关键概念

MEX (最小排除值): 集合中未出现的最小非负整数

例如: MEX([1,2,0,1,3,0]) 中窗口 [1,2,0] 的 MEX 是 3

输入输出

输入:

• 第一行: 测试用例数量 t (1≤t≤10⁴)

• 每个测试用例第一行: n 和 k ($2≤k≤n≤2×10⁵$)

• 每个测试用例第二行: n 个整数 $a₁,a₂,...,aₙ$ (0≤aᵢ≤n)

输出: 一个非负整数,表示可能的最大 MEX 值

思路讲解

哈哈，当你发现一道理应很简单的题目有这个比较复杂的决策的时候，这个时候需要想的是，这个决策是不是根本无关紧要？

哈哈，为什么决策根本无关紧要呢？因为答案肯定是 $≤k-1$ 的，因此我们需要的数字是 $0～k-2$，不过我们选择的区间长度是 $k$，因此如果区间里面数字全是 $[0,k-2]$，那必然有重复数字，删除重复的自然是不会对答案产生影响。如果有数字超过这个范围，那删除也更加没有影响。

因此其实最后的这个结果就是原数组 mex 值和 $k-1$ 中的最小值，

AC代码

AC
https://codeforces.com/contest/2183/submission/358042015

源代码

/**
 * Problem: B. Yet Another MEX Problem
 * Contest: Hello 2026
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2183/problem/B
 * Created: 2026-01-16 11:23:30
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    set<ll> st;
    for (int i=0;i<N+2;++i) {
        st.insert(i);
    }
    for (int i=0;i<N;++i) {
        cin>>A[i];
        st.erase(A[i]);
    }
    ll mex=*st.begin();
    cout<<min(mex,K-1)<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    while (lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2183/submission/358042015

*/

心路历程（WA，TLE，MLE……）