Минимальная сумма медиан всех возможных подпоследовательностей длины K отсортированного массива

Для данного отсортированного массива arr[] , состоящего из N целых чисел и положительного целого числа K (такого, что N%K равно 0 ), задача состоит в том, чтобы найти минимальную сумму медиан всех возможных подпоследовательностей размера K , таких что каждый элемент принадлежит только одна подпоследовательность.

Примеры:

Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 2
Output: 6
Explanation:
Consider the subsequences of size K as {1, 4}, {2, 5}, and {3, 6}.
The sum of medians of all the subsequences is (1 + 2 + 3) = 6 which is the minimum possible sum.

Input: K = 3, arr[] = {3, 11, 12, 22, 33, 35, 38, 67, 69, 71, 94, 99}, K = 3
Output: 135

Наивный подход: данная проблема может быть решена путем создания всех возможных отсортированных подпоследовательностей размера K и вывода медианы всех этих подпоследовательностей в качестве результата.

Временная сложность: O(2 ^N )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать, используя жадный подход для построения всех подпоследовательностей. Идея состоит в том, чтобы выбрать K/2 элементов из начального массива и K/2 элементов с конца массива так, чтобы медиана всегда находилась в первой части. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, res , которая хранит результирующую сумму медиан.
• Инициализируйте переменную, скажем, T как N/K , чтобы сохранить количество требуемых подпоследовательностей, и переменную D как (K + 1)/2 , чтобы сохранить расстояние между медианами.
• Инициализируйте переменную, скажем, i как (D – 1) , чтобы сохранить индекс первой медианы, которая будет добавлена к результату.
• Повторяйте до значения i < N и T > 0 и выполняйте следующие шаги:
  • Добавьте значение arr[i] в переменную res .
  • Увеличьте значение i на D , чтобы получить индекс следующей медианы.
  • Уменьшите значение T на 1 .
• После выполнения вышеуказанных шагов выведите в качестве результата значение res .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)