题解：CF2093E Min Max MEX

dengzheli · 2025-10-07 16:46:54 · 题解

题目传送门

一看到“最小值最大”，二分便是显而易见的了。

二分答案，然后就来写判断函数里的东西。

传进来了一个数x，接下来就是验证x的可行性。

考虑用s记录一共分了几个集合，ans记录当前集合的 MEX 。 之后，如果ans = x，就新开一个集合，再把之前的标记删掉。最后，如果x \le s，则返回真，否则为假。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int T, n, k, a[N], mx;
bool mp[N];
vector<int> v;
bool check(int x) {
    for(auto i : v) mp[i] = 0;
    v.clear();
    int s = 0, ans = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] <= 2e5) {
            v.push_back(a[i]);
            mp[ a[i] ] = 1;
        }
        while(mp[ans]) ans ++;
        if(ans >= x) {
            s ++;
            ans = 0;
            for(auto i : v) mp[i] = 0;
            v.clear();
        }
    }
    return (s >= k);
}
int main() {
    scanf("%d", &T);
    while(T --) {
        mx = 0;
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            mx = max(mx, a[i]);
        }
        int l = 0, r = min(mx + 1, 200000), mid;
        while(l < r) {
//          cout << l <<' ' << r <<' ' << mid <<'\n';
            mid = (l + r + 1) / 2;
            if(check(mid)) l = mid;
            else r = mid - 1;
        }
        printf("%d\n", l);
    }
    return 0;
}