MEX maximizing
主要题意
初始你有一个空序列,每一次往序列中加上一个数,你可以对序列中的数加或减 \(x\) 的任意倍数,你的任务是在每一次找到数组内不存在的最小整数,并且通过操作使最小整数最大。
主要思路
我们从 \(0\) 开始枚举,只要数组中不存在能变成这个数的数,那么这就是要找的最小整数,我们可以知道,对于 \(a\) 和 \(y\) 两个数,只要满足取余 \(x\) 等于 \(0\) 时,我们就可以将 \(a\) 加上或减去 \(x\) 的倍数就能变成 \(y\)。
代码
/*
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define re register
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
#define all(x) x.begin(), x.end()
#define fst \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef pair<int, int> PII;
const int N = 1e6 + 10;
const int M = 1e6 + 10;
const int Max = 1e3 + 5;
const int INF = 1e18, P = 998244353;
const double eps = 1e-6;
inline int read()
{
int x = 0;
bool f = true;
char c = getchar();
while (c < 48 || c > 57)
{
if (c == '-')
f = false;
c = getchar();
}
while (c >= 48 && c <= 57)
x = (x << 3) + (x << 1) + c - 48, c = getchar();
return f ? x : -x;
}
inline void write(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
inline void wsp(int x) { write(x), putchar(' '); }
inline void wel(int x) { write(x), putchar('\n'); }
int q, y, x;
int t[N];
int cnt = 0;
signed main()
{
fst;
q = read(), x = read();
while (q--)
{
y = read();
t[y % x]++;
while (t[cnt % x])
{
t[cnt % x]--;
cnt++;
}
cout << cnt << endl;
}
return 0;
}