Solução Apagando e Ganhando

0 Flares Facebook 0 0 Flares ×

Solução de Pedro Michael, comentários de Rogério Júnior

Para ver o problema original, clique aqui.

A ideia desta solução é gulosa. Vamos apagar um número se o número à sua direita (que ocupará seu lugar) for menor que ele, e daremos preferência para apagar números mais à esquerda porque aumentar o valor de casas mais à esquerda do número aumenta mais o valor que de casas mais à direita (aumentar as centenas de milhares é melhor que aumentar as dezenas).

Para fazer isso, vamos inserir um a um os algarismos da esquerda para a direita em uma pilha. Quando inserimos um número, se ele for maior que o número à sua esquerda (ou seja, o topo da pilha, pois foi o último a ser inserido) e ainda não houver d números apagados, apago este número, e continuo apagando enquanto o número a ser inserido for maior. Feito isso, só inserimos o novo número na pilha se o tamanho dela ainda for menor que n-d, que deve ser o tamanho final do número.

Se salvarmos a pilha como um array de char, basta adicionarmos o caractere '\0' ao final (para marcar o fim da string e imprimi-la com um printf. Segue o código para melhor entendimento.

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: