Codeforces 1294D - MEX maximizing 题解

还是大佬的思路强啊。

题解 #

我们可以得到所有模 $x$ 相同的数通过加或减 $x$ 所以我们只关注 $a_i\bmod x$ 。为了使 mex 最大化，我们需要从 0 开始尽可能长的连续的数。在模的意义下，也就是说 $1,2,3,4,\dots,x,1,2,3,4,\dots,x,\dots$ 。所以我们只需要保存同余类里的数的个数然后每次询问后尝试增加答案就行了。

Code #

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q, x;
    cin >> q >> x;
    vector<int> cnt(x);
    int ans = 0;
    while (q--) {
        int n;
        cin >> n;
        cnt[n % x]++;
        while (cnt[ans % x]) {
            cnt[ans % x]--;
            ans++;
        }
        cout << ans << endl;
    }
    return 0;
}