Разделите отсортированный массив на K частей, минимизировав сумму разности максимума и минимума в каждой части — набор 2.

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

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

Примеры:

Input: arr[] = { 10, 20, 70, 80 },  N = 4, K = 2
Output: 20
Explanation: The given array can be split in the following way
{10, 20} and {70, 80}. The differences are (20 – 10) = 10 and (80 – 70) = 10
The sum = 10 + 10 = 20

Input:  arr[] = { 5, 10, 50, 70 }, N = 4, K = 3
Output: 5
Explanation: The subarrays are {5, 10}, {50}, {70}
The differences are 10 – 5 = 5, 50 – 50 = 0, 70 – 70 = 0
The sum = 5 + 0 + 0 = 5

Подход: другие подходы обсуждаются в наборе 1 этой статьи. Здесь мы обсуждаем подход бинарного поиска.

Подход, оптимизированный для использования в пространстве: идея состоит в том, чтобы использовать бинарный поиск, чтобы найти ответ. Ответ лежит в [ 0, ( arr[N-1] – arr[0]) ]. См. следующее наблюдение для обоснования.

  • Assuming permission to make as many cuts as possible, the answer would be 0 because each element can form a subarray. Thus the minimum value would be 0.
  • Now the other extreme case can be when only one subarray is allowed, In this case, the answer would be (arr[N-1] – arr[0]). These were the two extreme cases and it is guaranteed that the answer would lie in between them.

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную ans как 0 , чтобы сохранить ответ.
  • Примените бинарный поиск с low = 0 и high = arr[N-1] – arr[0] .
  • Для каждого значения mid проверьте, может ли лента длины mid покрыть все отверстия в пределах K разрезов.
  • Если это так, то мы пришли к потенциальному ответу. Сохраните значение и проверьте, можно ли сделать то же самое для ленты меньшей длины. (сделать высокий = средний – 1 )
  • Если нет, то найдите большее значение для середины ( low = mid + 1 ).

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N*log(M)), где M — максимальное значение массива.
Вспомогательное пространство: O(1)

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