Estoque de Moedas

Solução escrita por Malu Azevedo

Conhecimentos necessários:

• Algoritmo guloso

O problema nos pede para determinar a quantidade máxima de moedas que Erika consegue armazenar em $N$ pilhas de forma estável, respeitando os limites máximos $h_i$ de cada pilha e a restrição de que a diferença entre a quantidade de moedas de pilhas adjacentes não pode ser maior do que 1.

Ideia Central

A ideia central para resolver o problema de forma ótima e eficiente consiste em aplicar uma abordagem gulosa utilizando duas varreduras lineares independentes, uma da esquerda para a direita e outra da direita para a esquerda. Como cada pilha impõe uma restrição sobre a sua altura máxima que se propaga para os vizinhos devido à regra de variação máxima de uma unidade, podemos ajustar os limites de forma incremental. Na primeira varredura, garantimos que nenhuma pilha ultrapasse a altura da pilha anterior acrescida de uma unidade, propagando o teto máximo da esquerda para a direita. Na segunda varredura, fazemos o oposto ao percorrer o vetor de trás para frente, assegurando que nenhuma pilha viole a restrição em relação à sua vizinha da direita. Ao combinar essas duas restrições propagadas, cada pilha assume automaticamente o maior valor possível que respeita tanto o seu limite original quanto as restrições impostas por todo o resto do vetor, bastando somar todas as alturas finais para obter a quantidade máxima total de moedas.

Abordagem Completa

Lemos a quantidade de pilhas $N$ e preenchemos o vetor de alturas $h$ utilizando o tipo long long para evitar estouros de capacidade. Em seguida, executamos um primeiro laço de 1 até $N-1$ verificando se a pilha atual excede a altura da anterior mais um (h[i] > h[i-1] + 1), atualizando-a para o valor máximo permitido caso a condição seja verdadeira. Logo após, executamos o segundo laço de $N-2$ até 0 checando se a pilha atual excede a altura da posterior mais um (h[i] > h[i+1] + 1), realizando a correção correspondente pela direita. Por fim, percorremos todo o vetor processado acumulando os valores em uma variável de soma moedas e imprimimos o resultado final. A complexidade de tempo é linear $O(N)$.

Clique aqui para ver o código completo.