Comentário NOIC - OBI Fase 3 P1 e P2 - Plano de estacionamento

plano.cpp

// Comentário NOIC - OBI Fase 3 PJ e P1 - Plano de estacionamento
// Complexidade: O(M log N)
// Escrito por Lúcio Figueiredo

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);

	set<int> st; // set com vagas não-ocupadas

	for (int i = 1; i <= n; i++)
		st.insert(i); // inserimos todas as vagas de 1 a N

	int ans = 0; // resposta

	for (int i = 1; i <= m; i++)
	{
		int v;
		scanf("%d", &v);

		// encontramos o primeiro elemento maior que V no set (função upper_bound)
		set<int>::iterator it = st.upper_bound(v);

		// se este elemento é o menor do set, não existem vagas livres menores ou iguais a V
		if (it == st.begin()) break;

		// senão, o elemento logo atrás é a maior vaga menor ou igual a V
		it--;
		ans++;

		// removemos esta vaga do set, pois agora está ocupada
		st.erase(it);
	}

	printf("%d\n", ans);
}