Solução por Lúcio Figueiredo
Conhecimento prévio necessário:
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: