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

😎 Решение:

class Solution {
    func maximizeSweetness(_ sweetness: [Int], _ k: Int) -> Int {
        func canDivide(_ minSweetness: Int) -> Bool {
            var currentSum = 0
            var cuts = 0
            for sweet in sweetness {
                currentSum += sweet
                if currentSum >= minSweetness {
                    cuts += 1
                    currentSum = 0
                }
            }
            return cuts >= k + 1
        }
        
        var left = sweetness.min()!
        var right = sweetness.reduce(0, +) / (k + 1)
        
        while left < right {
            let mid = (left + right + 1) / 2
            if canDivide(mid) {
                left = mid
            } else {
                right = mid - 1
            }
        }
        
        return left
    }
}

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