Solução Informática Nível Avançado - Semana 8

Solução por Lúcio Figueiredo

Conhecimento prévio necessário:

• Set

Imagine que foi criada uma configuração ótima de torres com $i-1$ cubos e que o cubo $i$ será inserido no próximo passo. Note que se o topo de todas as torres já criadas tem valor menor ou igual a $c_i$, teremos que criar uma nove torre com $i$ no topo. Caso contrário, podemos inserir $i$ no topo de alguma torre já criada (pois queremos minimizar a quantidade de torres). O que resta é decidir em qual torre inserir $i$.

É possível perceber que é sempre ótimo inserir o cubo $i$ na torre cujo valor de topo $x$ é o menor valor possível tal que $x > c_i$. Este fato é verdade pois ao inserir $c_i$ na torre de menor topo possível, não "desperdiçamos" torres com valor de topo maior, e portanto, aumentamos a chance de não se tornar necessário criar uma nove torre com um próximo cubo.

Assim, podemos utilizar um multiset que guarda os valores nos topos de cada torre (precisamos utilizar o multiset pois alguns topos podem possuir valores iguais). A operação de encontrar o menor topo maior que $c_i$ é simplesmente uma operação de upper_bound no set. Caso não exista valor maior que $c_i$ no set, simplesmente criamos uma nova torre inserindo $c_i$ no set. Complexidade: $O(n \log_{} n)$.

Confira o código abaixo para melhor entendimento: