題目
#

leetcode 1231 - Divide Chocolate(題目說明請點連結)

題目簡述
#

給定一個甜度陣列和需要分給的朋友數量，將巧克力切成 k+1 塊，使得每個人得到的巧克力甜度總和中的最小值最大化。

Example 1:

Input: sweetness = [1,2,3,4,5,6,7,8,9], K = 5
Output: 6
Explanation: 你可以將巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。

Example 2:

Input: sweetness = [5,6,7,8,9,1,2,3,4], K = 8
Output: 1
Explanation: 只有一種方式將巧克力切成9塊。

Example 3:

Input: sweetness = [1,2,2,1,2,2,1,2,2], K = 2
Output: 5
Explanation: 你可以將巧克力分成 [1,2,2], [1,2,2], [1,2,2]。

解題思路
#

輸入為一個sweetness的甜度陣列，與需要分給k個朋友(要包含自己)，
輸出為將巧克力切成 k+1 塊的所有人能得到甜度中的最小值。

此題思路與 leetcode410 類似，但要搜尋目標的不同。

比較Leetcode 410 與 Leetcode 1231
#

Leetcode 410：最小化最大值
更新邏輯：當找到可行解時，我們嘗試更小的最大值，右邊界 right=mid。
因為需要試探更小的範圍，用下取中間值。
Leetcode 1231：最大化最小值
更新邏輯：當找到可行解時，我們嘗試更大的最小值，左邊界 left=mid。
因為需要試探更大的範圍，用上取中間值。

這裡搜尋最大化最小值將二分法設定範圍如下：

左邊界（min）：陣列之中的最小甜度。
- min=min(sweetness)
右邊界（max）：所有甜度的總和。
- max=∑(sweetness)

二分搜索過程：

初始化二分範圍為 [min,max]。
計算中間值 mid=(min+max+1)/2。
建立canSplit方法驗證 mid 是否可行：
- 如果可行，更新左邊界 min=mid，嘗試更大甜度。
- 如果不可行，更新右邊界 max=mid-1。
最後當 min(left)==max(right)，找到答案

例子說明
#

sweetness = [1,2,3,4,5,6,7,8,9], k = 5

初始情況：left = 1（最小甜度），right = 45（總甜度）

第一次二分：mid = 23
- 檢查是否能分成 6 塊，每塊甜度至少 23
- 不可行，right = mid - 1 = 22
第二次二分：mid = 11
- 檢查是否能分成 6 塊，每塊甜度至少 11
- 可行，left = mid = 11
第三次二分：mid = 16
- 檢查是否能分成 6 塊，每塊甜度至少 16
- 可行，left = mid = 16
繼續二分…
- 最終找到最大可行值 6
最終結果：
- 返回 6

完整程式碼
#

java

class Solution {
    public int maximizeSweetness(int [] sweetness, int k) {
        int left = Integer.MAX_VALUE; // 初始化左邊界為最大值
        int right = 0; // 初始化右邊界為0

        for (int sweet : sweetness) { // 遍歷甜度數組
            if (sweet < left) { // 找到最小甜度
                left = sweet;
            }
            right += sweet; // 累計總甜度
        }

        while (left < right) { // 當left小於right時繼續搜索
            int mid = left + (right - left + 1) / 2; // 計算中間值，使用上取整
            if(canSplit(sweetness, k, mid)) { // 檢查是否能分成k+1塊，每塊甜度至少mid
                left = mid; // 如果可行，嘗試更大的最小值
            } else {
                right = mid - 1; // 如果不可行，嘗試更小的最大值
            }
        }

        return left; // 返回最大可行值
    }
    
    public boolean canSplit(int [] sweetness, int k, int minSweetness) {
        int count = 0; // 記錄已分割的塊數
        int sum = 0; // 當前塊的甜度總和

        for(int sweet : sweetness) { // 遍歷甜度數組
            sum += sweet; // 累加當前甜度
            if(sum >= minSweetness) { // 如果當前塊的甜度達到最小值
                sum = 0; // 重置當前塊的甜度
                count++; // 增加塊數
            }
        }

        if(count >= k + 1) { // 如果能分成至少k+1塊
            return true; // 可行
        }

        return false; // 不可行
    }
}