Задача: 1231. Divide Chocolate
Сложность: 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 частей имела сладость не меньше текущего значения.

😎 Решение:

function maximizeSweetness($sweetness, $k) {
    $canDivide = function($minSweetness) use ($sweetness, $k) {
        $currentSum = 0;
        $cuts = 0;
        foreach ($sweetness as $sweet) {
            $currentSum += $sweet;
            if ($currentSum >= $minSweetness) {
                $cuts++;
                $currentSum = 0;
            }
        }
        return $cuts >= $k + 1;
    };

    $left = min($sweetness);
    $right = intdiv(array_sum($sweetness), $k + 1);

    while ($left < $right) {
        $mid = intdiv($left + $right + 1, 2);
        if ($canDivide($mid)) {
            $left = $mid;
        } else {
            $right = $mid - 1;
        }
    }

    return $left;
}

Ставь 👍 и забирай 📚 Базу знаний