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

## 题目大意

### 问题描述

给定长度为 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](https://codeforces.com/contest/2183/submission/358042015)



::: 源代码

```cpp
/**
 * 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……）