Надо найти сумму всех abs(a[i] - Х), где X - то самое число, которое окажется посередине, если массив отсортировать (то есть медиана).
Оное число, если не ошибаюсь, можно найти линейно с помощью QuickSelect. Если массив нельзя перемешивать, придется сделать его копию.
