Отсортируем массив. Сделаем бинпоиск по ответу пусть медиана равна $x$. Числа до центрального не стоит увеличивать, так это не выгодно. Все остальные числа стоит увеличить до значения $x$, если текущее значение меньше. Другими словами взять по всем после половины $max(0,x-a_i)$.

Асимптотика $O(n\log k)$.