Разделить массив на K подмассивов, чтобы минимизировать сумму разницы между минимальным и максимальным

Опубликовано: 25 Февраля, 2023

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

Примечание. Каждый элемент массива должен быть включен в один подмассив, и каждый подмассив не должен быть пустым.

Примеры:

Input: arr[] = {5, 9, 16, 17, 24, 43}, K = 3 
Output: 12
Explanation: {5, 9}, {16, 17, 24}, {43} are the three subarrays because 
(9-5) + (24-16) + (43-43) = 12 is minimum of all possible subarrays.

Input: arr[] = [5, 7, 8, 8, 11, 14, 22}, K = 3
Output: 13
Explanation: {5, 7}, {8, 8}, {11, 14, 22}. So, (7 – 5) + (8 – 8) + (22 – 11) = 13  
The given array of length 5 cannot be split into subsets of 4. 

Подход: Задача может быть решена на основе следующей идеи:

We have to choose K-1 indexes from the array to form K subarrays.

If N is the length of the array and suppose we have chosen K-1 indices (i.e.  a < b < . . . < c) then the required sum of K-subarrays will be 
(arr[a] – arr[0]) + (arr[b] – arr[a+1]) + . . . + (arr – arr[b+1]) + (arr[N-1] – arr).

On rearranging: (arr[N-1] – arr[0]) +(arr[a] – arr[a+1]) + (arr[b] – arr[b+1]) + . . . + (arr – arr)).

So, initially answer is  sum = arr[N-1] – arr[0] and to minimize the answer add K – 1 minimum pairs to sum.

Для реализации идеи выполните следующие шаги:

  • Создайте массив и сохраните разницу между соседними элементами.
  • Отсортируйте массив разностей.
  • Выберите первые K элементов из массива.
  • Добавьте эти значения к разнице между arr[N-1] и arr[0] .

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

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

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