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 
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 
, que deve ser o tamanho final do número.
Se salvarmos a pilha como um 
de 
, basta adicionarmos o caractere '\0' ao final (para marcar o fim da 
e imprimi-la com um 
. Segue o código para melhor entendimento.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #define MAX 100100 | |
| int main(){ | |
| // variáveis que vou usar | |
| char pilha[MAX], num; | |
| int topo, n, d, apagados, i; | |
| // enquanto houver entrada | |
| while(scanf("%d%d", &n, &d) && (n+d)){ | |
| // a quantidade de números apagados começa zero | |
| apagados = 0; | |
| // para cada algarismo do número | |
| for(i = 0, topo = -1; i < n; i++){ | |
| // leio seu valor | |
| scanf(" %c", &num); | |
| // enquanto houver algum número na pilha, ainda não houver d apagados | |
| // e o algarismo atual for maior que o topo da pilha | |
| while(topo > -1 && apagados < d && num > pilha[topo]){ | |
| // apago o número que está no topo da pilha | |
| topo--; | |
| // e aumento a quantidade de números apagados | |
| apagados++; | |
| } | |
| // se o tamanho da pilha for menor que n-d | |
| // insiro o novo número na pilha | |
| if(topo+1 < n-d) pilha[++topo] = num; | |
| } | |
| // por fim, adiciono '\0' ao fim da pilha | |
| pilha[++topo] = '\0'; | |
| // para imprimi-la só com um printf | |
| printf("%s\n", pilha); | |
| } | |
| return 0; | |
| } |