Letras

letras.cpp

// Letras - F2P1 - OBI 2015
// Rogério Júnior
// Complexidade: O(n log n)

#include <cstdio> // scanf e printf
#include <algorithm> // upper_bound
#include <vector> // vector
#include <cstring> // strlen

using namespace std; // para uso do C++

#define PB push_back // por simplicidade
#define MAXN 300300 // defino o valor de MAXN

// declaro as variáveis que vou usar
vector<char> pilha;

int n;

char frase[MAXN];

int main(){
	
	// leio a string da entrada
	scanf(" %s", frase);
	
	// defino n como o tamanho da frase
	n=strlen(frase); 
	
	// para cada elemento
	for(int i=0; i<n; i++){
		
		// guardo seu valor em x
		char x = frase[i];
		
		// declaro um iterador que guardará o elemento mais à esquerda de pilha
		// que não é menor que x
		vector<char>::iterator it = upper_bound(pilha.begin(), pilha.end(), x);
		
		// se it for o fim do vector, então não há elemento que não seja menor que x
		// ou seja, todos os topos de pilha são menores ou iguais a x
		
		// logo, criamos uma nova pilha e colocamos x no seu topo
		if(it==pilha.end()) pilha.PB(x);
		
		// porém, se it apontar para alguma posição válida do vector
		// colocamos x no topo desta pilha, substintuindo o valor que it aponta por x
		else *it = x;
	}
	
	// no fim, basta imprimir a quantidade de pilhas
	printf("%d\n", pilha.size());
	
	return 0;
}