题目意思理解
之前让我比较困惑的是mex的定义
mex(A)是求集合A中未出现的最小非负整数m,而这个非负整数m并不需要满足在A中
比如A={1,2,3,4} 那么mex(A)=0,0并不在A中,因此在遍历的时候是从0到100(到110)也无所谓,
因为mex(集合)<=100
对于一个集合B
那么从前往后遍历(0-100),当遇到第一个B中没有出现的整数时返回答案,则为mex(B);
在弄明白mex怎么计算之后
然后再考虑将集合进行划分的方式
将原集合划分成A,B,并且对于集合中的元素,从小到大考虑
对于原集合中的每一个数x而言
如果x的个数等于1,那么放入A中,这样mex(A)>x (说明mex(A)>x的前提是A中有0~x-1的数,下同)
如果x的个数大于1个,A和B都放x,这样mex(A)>x,mex(B)>x
这么做会使得mex(A)最大,然后在mex(A)最大的情况下mex(B)最大
java 代码
import java.util.*;
import java.io.*;
import java.math.*;
public class Main{
static int N = 100+10;
static int[] arr = new int[N];;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
int n = sc.nextInt();
Arrays.fill(arr,0);
while(n-- >0){
int x = sc.nextInt();
arr[x]++;
}
System.out.println(mex()+mex());
}
}
static int mex(){
for(int i=0;i<N;i++){
if(arr[i] == 0) return i;
else arr[i]--;
}
return -1;
}
}