Solução por Thiago Mota
Uma solução gulosa sempre diminui o maior número e incrementa o menor, enquanto necessário. A resposta pode ser muito grande, então simplesmente simular as operações não se encaixa no limite de tempo.
No entanto, podemos tentar melhorar essa ideia. Em vez de executar operação por operação, podemos construir um vetor de frequências $$F$$ que guarda o número de vezes que aquele número aparece, se $$a$$ for o menor valor e $$b$$ for o maior valor e $$c = min(F_a, F_b)$$, podemos aumentar $$c$$ valores $$l$$ e diminuir $$c$$ valores $$r$$ custando $$c$$ operações, com isso sempre diminuiremos o maior valor ou aumentaremos o menor.
Para isso podemos utilizar Two Pointers para o mínimo e para o máximo, e sair mudando a frequência dos valores, a complexidade fica em $$O(n + |r – l|)$$ sendo $$|r – l|$$ a diferença entre o maior e o menor valor, como os valores vão até $$10^5$$, a complexidade passará no tempo da questão. Segue o código:
https://gist.github.com/Thiago4532/8dc74ea11cb73d97b5801f0b3fcb13a8