Сложность: hard
У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.
Пример:
Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6
👨💻 Алгоритм:
1⃣Для решения задачи мы можем использовать метод двоичного поиска для определения максимальной минимальной сладости, которую можно получить.
2⃣Двоичный поиск:
Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения.
3⃣Проверка делимости:
Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения.
😎 Решение:
def maximizeSweetness(sweetness, k):
def canDivide(minSweetness):
current_sum = 0
cuts = 0
for sweet in sweetness:
current_sum += sweet
if current_sum >= minSweetness:
cuts += 1
current_sum = 0
return cuts >= k + 1
left, right = min(sweetness), sum(sweetness) // (k + 1)
while left < right:
mid = (left + right + 1) // 2
if canDivide(mid):
left = mid
else:
right = mid - 1
return left
Ставь 👍 и забирай 📚 Базу знаний