Solução Informática - Nivel Intermediário - Semana 25

Escrito por Lúcio Figueiredo

Conhecimento prévio necessário:

• Ordenação

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: