Сложность: 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 частей имела сладость не меньше текущего значения.
😎 Решение:
public class Solution {
public int maximizeSweetness(int[] sweetness, int k) {
int left = Arrays.stream(sweetness).min().getAsInt();
int right = Arrays.stream(sweetness).sum() / (k + 1);
while (left < right) {
int mid = (left + right + 1) / 2;
if (canDivide(sweetness, k, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private boolean canDivide(int[] sweetness, int k, int minSweetness) {
int currentSum = 0, cuts = 0;
for (int sweet : sweetness) {
currentSum += sweet;
if (currentSum >= minSweetness) {
cuts++;
currentSum = 0;
}
}
return cuts >= k + 1;
}
}Ставь 👍 и забирай 📚 Базу знаний