Минимальная сумма расстояний между каждым элементом массива и множествами из К-элементов этого массива

Всем привет! Еще одна модификация одной из самых распространённых задач.
(Минимальная сумма абсолютных разностей между элементом и подмножеством элементов массива)

У нас есть целочисленный неотсортированный массив положительных чисел.
Для каждого элемента массива нужно найти минимальную сумму расстояний от этого элемента до множества элементов массива размера К, не содержащих этот элемент.

То есть:
Массив = {5, 7, 4, 9}
К = 2

min_sum(5) = dist(5, {4, 7}) = |5-4|+|5-7|=3
min_sum(7) = dist(7, {9, 5}) = |7-9|+|7-5|=4
min_sum(4) = dist(4, {5, 7}) = |4-5|+|4-7|=4
min_sum(9) = dist(9, {7, 5}) = |9-7|+|9-5|=6

Наивным решением было бы отнять от всех элементов массива i-тый элемент, затем отсортировать такой массив и посчитать суммы первых К элементов в отсортированном массиве. И так для каждого индекса. Но это работает только для маленьких массивов...

Если сперва отсортировать массив, тогда можно будет рассматривать только +-k элементов вокруг i-того элемента. Но k может быть размера вплоть до размера самого массива.

Можно хранить массив разностей между элементами отсортированного массива, но не понимаю можно ли это использовать эффективно.

Ограничение на входные данные:
n - количество элементов массива
k - размер подмножеств
a[i] - элемент массива

2 <= n <= 350 000
1 <= k < n
1 <= a[i] <= 10^9

Ограничение по времени: 2 сек.

С таким ограничением нужно как-то решить эту задачу быстрее, чем за O(n^2)

Буду благодарен, если у кого-нибудь есть идея, как это можно реализовать эффективно, какие структуры данных в С++ использовать лучше.

0