Solução Informática - Nível Intermediário - Semana 41

Solução escrita por João Pedro Castro

Conhecimento prévio necessário:

• Algoritmo Guloso
• Soma de Prefixo

Podemos perceber que só precisamos considerar a compra de um pacote $i$ se não existe nenhum outro pacote $j$ tal que $i < j$ e $c_i \leq c_j$, já que sempre será mais vantajoso comprar o pacote $j$, que tem mais doces e é mais barato (ou tem o mesmo preço); vamos guardar os pacotes que são considerados do menor para o maior em um array $s$. Agora, podemos usar a ideia gulosa de comprar a quantidade máxima possível de um pacote $s_i$ para $1 \leq i \leq |s|$, e depois usando o resto de $c_{s_i}$ pela quantidade restante de moedas $k$ para comprar o próximo pacote $s_{i+1}$; e como comprar o próximo pacote $x$ vezes é melhor do que comprar o pacote atual $x$ vezes, podemos simplesmente usar a expressão a seguir para descobrir quanto iremos comprar do pacote $s_i$:

$\lfloor \frac{k}{c_{s_i}} \rfloor - min(\lfloor \frac{k}{c_{s_i}} \rfloor, \lfloor \frac{k~mod~c_{s_i}}{c_{s_{i+1}} - c_{s_i}} \rfloor)$

E então usar soma de prefixo para escrever o maior array lexicograficamente possível.

Clique aqui para conferir o código