Минимизируйте затраты на сокращение массива, заменив два элемента суммой не более K раз для любого индекса.

Опубликовано: 20 Сентября, 2022

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

Пример:

Input: arr[] = {3, 6, 4, 1, 1}, N = 5, K = 2
Output: 11
Explanation: Sum of the array can be collected as follows:

  • Pick element at index 4 and add it to element at index 2 i.e (1 ⇢ 4) = 1+4 = 5, cost = 1 and arr[] = {3, 6, 5, 1, 0}.
  • Pick element at index 3 and add it to element at index 2 i.e (1 ⇢ 5) = 1+5 = 6, cost = 1+1 = 2 and arr[] = {3, 6, 6, 0, 0}.
  • Pick element at index 0 and add it to element at index 1 i.e (3 ⇢ 6) = 3+6 = 9, cost = 2+3 = 5 and arr[] = {0, 9, 6, 0, 0}.
  • Pick element at index 2 and add it to element at index 1 i.e (6 ⇢ 9) = 6+9 = 15, cost = 5+6 = 11 and arr[] = {0, 15, 0, 0, 0}.

Input: arr[] = {5, 3, 2, 1, 4, 6}, N = 6, K = 3
Output: 18
Explanation: Sum can be collected as follows

  • Pick element at index 3 and add it to element at index 4 i.e (1 ⇢ 4) = 1+4 = 5, cost = 1 and arr[] = {5, 3, 2, 0, 5, 6}.
  • Pick element at index 2 and add it to element at index 0 i.e (2 ⇢ 5) = 2+5 = 7, cost = 1+2 = 3 and arr[] = {7, 3, 0, 0, 5, 6}.
  • Pick element at index 1 and add it to element at index 5 i.e (3 ⇢ 6) = 3+6 = 9, cost = 3+3 = 6 and arr[] = {7, 0, 0, 0, 5, 9}.
  • Pick element at index 4 and add it to element at index 5 i.e (5 ⇢ 9) = 5+9 = 14, cost = 6+5 = 11 and arr[] = {7, 0, 0, 0, 0, 14}.
  • Pick element at index 0 and add it to element at index 5 i.e (7 ⇢ 14) = 7+14 = 21, cost = 11+7 = 18 and arr[] = {0, 0, 0, 0, 0, 21}.

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

Задача состоит в том, чтобы получить такую конфигурацию дерева, чтобы к каждой вершине было подвешено не более K поддеревьев , а сумма произведений чисел, записанных на вершинах, и глубины вершин (где глубина корня равна 0) была минимальной. Чтобы минимизировать сумму:

  • вершины с большим номером не должны иметь большей глубины, чем вершины с меньшим номером (иначе их можно поменять и получить меньшую сумму).
  • каждая внутренняя вершина, кроме, может быть, одной, имеет ровно k потомков. (В реальной реализации нет необходимости строить дерево, нам нужно только знать, что это дерево.)

Теперь вычислите сумму для этой конфигурации. Чтобы сделать это, выполните следующие действия:

  • Прибавить к ответу сумму элементов с 1-го по k -й (в массиве с нулевым индексом, отсортированном по невозрастанию), умноженную на 1 ; затем сумма размеров следующих k стопок, умноженная на 2; и так далее до конца массива.
  • Чтобы получить ответ о сумме сегментов, используйте префикс суммы после сортировки массива.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ