分析:
-
题目翻译一下就是:把原来的数组分成两个数组,取划分后两个数组中不存在的最小的非负数。
-
再翻译一下就是:把原来的数组划分成两个数组,第一个是 a1, 第二个是 a2, 每个数组中第一次出现 元素值与下标值不等 的时候,下标值就是mex 的值。
解题思路:
模拟构造两个数组,找出每个数组的 mex 值,求和后输出。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
unordered_map<int, int> h;
int main()
{
int T;
cin >> T;
while(T--)
{
for(int i = 0; i <= 100; i++)
{
h[i] = 0;
}
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
int x;
cin >> x;
h[x] ++;
}
int a1 = 0, a2 = 0;
for(int i = 0; i <= 100; i++)//模拟构造第一个连续数组。
{
if(h[i] >= 1)
{
h[i]--;
}
else
{
a1 = i;
break;
}
}
for(int i = 0; i <= 100; i++)//模拟构造第二个连续数组
{
if(h[i] >= 1)
{
h[i]--;
}
else
{
a2 = i;
break;
}
}
cout << a1 + a2 << endl;
}
return 0;
}
这代码没有bug?
试试hack数据:
[1 1 2 2 … 100 100]
应该是[0 0 1 1 2 2 … 49 49]
一开始我也这么认为,所以让i从0到101,但是n<=100,意味着0-101的值不可能都出现两次以上,而如果是0-49都出现两次,那么楼主的代码是可以过的