思路
首先按照 $0 ~ 100$ 统计原数组的数值分布,然后再按照 $0 ~ 100$ 进行遍历,
当遍历到的数字在原数组中出现的次数 >= 2,则两个子集的mex值都会 +1
当遍历到的数字在原数组中出现的次数 = 1,则其中一个子集的mex值到达上限并固定
当遍历到的数字在原数组中出现的次数 = 0,则两个子集的mex值都会到达上限并固定。
代码 + 注释
t = int(input())
for idt in range(t):
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (101)
for i in range(n):
cnt[a[i]] += 1 # 记录数组的数值分布
ans = [-1] * 2 # 分别存储两个子集的mex值
for i in range(101):
if cnt[i] >= 2: # 如果该数字出现次数>=2,则两个子集的mex值都+1
continue
elif cnt[i] == 1: # 如果该数字出现次数=1,则第一个子集mex值固定
if ans[0] == -1:
ans[0] = i
else: # 如果该数字出现次数=0,则两个子集的mex值都会固定
if ans[0] == -1:
ans[0] = i
if ans[1] == -1:
ans[1] = i
break
print(sum(ans))