Solução Apagando e Ganhando

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.

https://gist.github.com/rogerioagjr/32a1656692457c62c68e