Найдите максимальную высоту, чтобы разрезать все шоколадки по горизонтали так, чтобы осталось не менее K штук.

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

Примеры:

Input: K = 7, arr[] = [15, 20, 8, 17]
Output: 15
Explanation:
Suppose a cut is made at height 8:
-> chocolate taken from 1st chocolate bar = 15 – 8 =7
-> chocolate taken from 2nd chocolate bar = 20 – 8 =12
-> chocolate taken from 3rd chocolate bar = 8 – 8 = 0
-> chocolate taken from 4th chocolate bar = 17 – 8 = 9
=> Total chocolate wasted = (7 + 12 + 0 + 9) – K = 28 – 7 = 21

Suppose a cut is made at height 15:
-> chocolate taken from 1st chocolate bar = 15 – 15 = 0
-> chocolate taken from 2nd chocolate bar = 20 – 15 = 5
-> 3rd chocolate bar wont be chosen as it is less than 15
-> chocolate taken from 4th chocolate bar = 17 – 15 = 2
=> Total chocolate wasted = (0 + 5 + 2) – K = 7 – 7 = 0

Therefore when we take chocolate of height 15 then chocolate wasted is minimum. Therefore 15 is the answer.

Input: K = 12, arr[] = [30, 25, 22, 17, 20]
Output: 21
Explanation:

After a cut at height 18, the chocolate removed is 25 and chocolate wastage is (25 – 12) = 13 units. But if the cut is made at height 21 is made then 14 units of chocolate is removed and the wastage is (14 – 12) = 2 which is the least, hence 21 is the answer

Подход: Данная проблема может быть решена на основе бинарного поиска.

The idea is to perform the Binary Search over then range [0, max element of the array] and find that value in the range, say M, such that the sum of remaining chocolate after making the horizontal cut at M gives minimum difference with K. 

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

• Инициализируйте две переменные, скажем, low и high как 0 и максимальный элемент массива соответственно.
• Повторяйте до low <= high и выполняйте следующие шаги:
  • Найдите значение mid как (low + high)/2 .
  • Найдите сумму оставшихся шоколадок после горизонтального разреза на высоте M .
  • Если значение M меньше K , то обновите значение high как (mid – 1) . В противном случае обновите значение low как (mid + 1) .
• После выполнения вышеуказанных шагов напечатайте значение равное полученной максимальной высоте , которую необходимо обрезать.

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

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