Escrito por Lúcio Figueiredo
Conhecimento prévio necessário:
A solução deste problema utiliza o seguinte lema:
Lema: Defina $$k$$ como o valor final que todos os gravetos possuirão após as operações. O valor $$k$$ que minimiza o custo das operações é a mediana dos valores iniciais dos gravetos.
A mediana de um conjunto de $$n$$ inteiros é o valor que se encontra na posição $$floor(\frac{n}{2})$$ do mesmo conjunto após ser ordenado crescentemente.
Assim, sendo $$med$$ a mediana do conjunto de números dado, o lema acima nos indica que o menor custo necessário é igual a $$\sum_{i=1}^n abs(a_i – med)$$.
Como é possível encontrar a mediana do vetor em $$O(n \log_{} n)$$ (só é necessário ordená-lo), a complexidade final é $$O(n \log_{} n)$$. Confira o código abaixo para melhor entendimento: