我们发现上述过程主要运用了权值，所以考虑使用 map 来维护每个值对 x 取余出现的次数，同时注意按照大小顺序来（保证上文中 a_t<k）。
English Statement
The main meaning
You are given an array a with n non-negative elements.
You can do following operation (in every operations the x are the same):
We should output the maximum of \operatorname{MEX}(a).
### The problem analysis
Obviously, to reach the maximum $\operatorname{MEX}(a)$ that $a$ should to be $0\sim n-1$.
And if we must kick some of them out, the smaller integers are the more important.
Try Greedy Algorithm: For $k$, if $k$ is in $a$, continue; if $k$ isn't, find $a_t \equiv k\pmod{x}$(Pay attention that $a_t<k$ is necessary).
We find that all the information in the Greedy Algorithm is values, but not ID, we can use STL `map` to count the number of the values modulo $x$.
## 代码实现
Here is my code.
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,x,a[200001];
map<int,int>mp1,mp2;
void Main(){
mp1.clear(),mp2.clear();
cin>>n>>x;
int pos=0;
for(int i=1;i<=n;i++){
cin>>a[i];
mp1[a[i]]++;//记录数出现的次数 Count the number of the values
}
sort(a+1,a+n+1);
for(int i=0;i<=n;i++){
if(mp1[i]){
mp1[i]--;
mp2[i%x]+=mp1[i];//记录模x的剩余值 Count the rest of the numbers modolo x
continue;
}
if(mp2[i%x]>=1){
mp2[i%x]--;
goto g;//使用剩余值 Use the rest numbers
}
cout<<i<<'\n';//无法让 i 进入 a Can't let i get into a (the MEX will be i)
break;
g:continue;
}
return;
}
signed main(){
for(cin>>T;T;--T)
Main();
return 0;
}
```
如有程序方面的问题、语法问题，欢迎私信。
If there are any mistakes about my program or grammar mistakes, pls [chat to me](/chat?uid=743014).
Updated: Edited some grammar mistakes.