Способность отправлять посылки в течение D дней

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

Примеры:

Input: arr[] = {1, 2, 1}, D = 2
Output: 3
Explanation:
Consider the minimum weight required by the boat as 3, then below is the order of weights such all the weight can be shipped within D(= 2) days:
Day 1: Ship the weights of values 1 and 2 on the first day as the sum of weights 1 + 2 = 3(<= 3).
Day 2: Ship the weights of value 1 on the second day as the sum of weights 1(<= 3).
Considering the minimum weight amount as 3, ships all the weight within D(= 2) days. Therefore, print 3.

Input: arr[] = {9, 8, 10}, D = 3
Output: 10

Подход: Данную проблему можно решить с помощью жадной техники и бинарного поиска. Можно заметить монотонность задачи: если все посылки могут быть успешно отправлены в течение D дней с вместимостью K , то они определенно могут быть отправлены с любой вместимостью, превышающей K . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем , как -1 , чтобы сохранить результирующую минимальную требуемую вместимость лодки.
• Инициализируйте две переменные, скажем, s и e максимальным элементом в данном массиве и общей суммой массива соответственно, которая обозначает нижнюю и верхнюю границы пространства поиска.
• Повторяйте, пока значение s не станет меньше или равно e , и выполните следующие шаги:
  • Инициализируйте переменную, скажем, mid как (s + e)/2 .
  • Проверьте, возможно ли отправить все посылки в течение D дней, когда максимально допустимая вместимость равна середине . Если установлено, что это правда , то обновите значение ans до mid и значение e до (mid – 1) .
  • В противном случае обновите значение s до (mid + 1) .
• После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

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

Временная сложность: O(N*log(S – M)), где S – сумма элементов массива, а M – максимальный элемент массива .
Вспомогательное пространство: O(1)