Разделить массив на K подмассивов, чтобы минимизировать сумму разницы между минимальным и максимальным
Для данного отсортированного массива 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)