Solução Informática - Nivel Iniciante - Semana 22

Escrito por Leonardo Paes.

Vamos armazenar a frequência de cada número de $0$ até $100$ no vetor $freq$. Agora $mex (A)$ seria o menor $i$ para o qual $freq_i = 0$. Seja este $i = x$ . $mex (B)$ seria o menor $i$ para o qual $freq_i \leq 1$. Isso ocorre porque uma contagem de cada número menor que $x$ iria para A, portanto, o elemento que estava presente inicialmente uma vez agora não estaria disponível para $B$.

Código de exemplo:

	#include <bits/stdc++.h>
	using namespace std;
	int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t;
	cin >> t;
	while(t--){
	int n;
	cin >> n;
	vector<int> freq(101, 0);
	for(int i=0; i<n; i++){
	int val;
	cin >> val;
	freq[val]++;
	}
	int a = 0, b = 0;
	while(freq[a] > 0) a++;
	while(freq[b] > 1) b++;
	cout << a + b << "\n";
	}
	return 0;
	}

view raw Mex de Subconjuntos.cpp hosted with by GitHub