Solução Balões

Solução por Roger Benet, comentário de João Guilherme

Inicialmente salvamos as alturas em um set e também guardamos sua frequência. Então para cada altura, vemos se a frequência dela é maior que 0, se for nós aumentamos a resposta e vemos quais balões serão estourados por essa agulha, reduzindo sua frequência.

Segue código para melhor entendimento.


#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000100
set<int> s;
int altura[MAXN],cont[MAXN];
int n,ans;
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &altura[i]);
cont[altura[i]]++;
s.insert(altura[i]);
}
set<int>::iterator it;
for(int i = 0; i < n; i++){
if(cont[altura[i]] != 0){
int x = altura[i];
ans++;
cont[x]--;
while(true){
x--;
it = s.find(x);
if(it != s.end() && cont[x] > 0)
cont[x]--;
else break;
}
}
}
printf("%d\n",ans);
return 0;
}