題目資訊

• 題目編號: 2226
• 題目連結: Maximum Candies Allocated to K Children
• 主題: Array, Binary Search

題目敘述

你有一個 0-索引 整數數組 candies。數組中的每個元素表示一堆糖果的大小 $candies[i]$。你可以將每一堆糖果分成任意數量的 子堆，但你 不能 將兩堆糖果合併在一起。

你還有一個整數 $k$。你應該將糖果分配給 $k$ 個小孩，使得每個小孩獲得的糖果數量 相同。每個小孩只能從 一堆 糖果中分得糖果，並且有些糖果堆可能會被未使用。

返回每個小孩可以獲得的糖果的最大數量。

範例 1:

輸入: candies = [5,8,6], k = 3
輸出: 5
解釋: 我們可以將 candies[1] 分成大小為 5 和 3 的兩堆，將 candies[2] 分成大小為 5 和 1 的兩堆。現在我們有五堆大小為 5, 5, 3, 5 和 1 的糖果堆。我們可以將三堆大小為 5 的糖果分配給三個小孩。可以證明每個小孩無法獲得超過 5 顆糖果。

範例 2:

輸入: candies = [2,5], k = 11
輸出: 0
解釋: 有 11 個小孩，但總共只有 7 顆糖果，因此不可能確保每個小孩至少獲得一顆糖果。因此，每個小孩都不能獲得糖果，答案是 0。

限制條件:

• $1 \leq candies.length \leq 10^5$
• $1 \leq candies[i] \leq 10^7$
• $1 \leq k \leq 10^{12}$

直覺

這個問題要求我們在給定的分配條件下，確定每個小孩最多可以分得多少糖果。主要挑戰在於確保恰好有 $k$ 個小孩可以得到相同數量的糖果，而糖果來自可以拆分但不能與其他堆合併的單一糖果堆。最佳的方法是在每個小孩可以分得的糖果數量上使用二分搜尋法，利用以下觀察：如果每個小孩可以分得 $t$ 個糖果是可行的，那麼更少的糖果也是可行的；反之，若不可行，那麼更多的糖果也是不可行的。

解法

主要的方法是在每個小孩可能接收的糖果數量上應用二分搜尋技術。以下是詳述的步驟：

1. 輔助函數 check: 這個輔助函數用來判定是否可以從給定的糖果堆分配至少 $t$ 個糖果給每位小孩。該函數遍歷每一堆糖果，計算每堆糖果可以分得 $t$ 個糖果的孩子數量，並對 $k$ 進行減法操作。如果所有 $k$ 個孩子都能在此方式下得到滿足，函數會返回 true。在邊界情況下，如果 $t = 0$ 則立即返回 false，因為無法分配任何糖果。

2. 確定跳躍大小: 開始時將跳躍大小設定為最大糖果堆的大小，這代表了如果將該堆分配給單一小孩，所能獲得的糖果上限。

3. 二分搜尋與衰減步長:

   • 將 ans 初始化為零，這會最終保存每個小孩可以分得的最多糖果數量。
   • 進行迭代循環，在每個給定的 jump 大小下，檢查是否可以使用 check 函數分配 ans + jump 糖果給每個孩子。
   • 如果條件符合，則將 ans 增加當前的 jump 大小，實際上增大了下限，並尋找更大的可行分配。
   • 在每次迭代中將 jump 大小除以 2，逐步進行更精細的探索，直到精度達到 1，保證結果收斂到最大可行值。

4. 返回結果: 循環結束後，ans 會包含在給定條件下最大可分配給每位小孩的糖果數量，並將其作為解返回。

這種方法通過使用對數搜索空間減少與在每一步中的貪婪分配檢查相結合，能夠高效地找到符合約束的最優解。

程式碼

C++

class Solution {
public:
    // 函數用來檢查是否能夠分配糖果，使得每位小孩恰好得到 't' 個糖果
    bool check(vector<int>& candies, long long k, int t) {
        if (t == 0) return false; // 如果每位小孩分不到糖果，則返回 false
        for (int c : candies) {
            k -= c / t; // 減少需要分配的小孩數量，由每堆糖果能滿足的小孩數決定
        }
        return (k <= 0); // 若所有小孩都能滿足，則返回 true
    }
    
    // 函數用來找出每位小孩可以得到的最大糖果數量
    int maximumCandies(vector<int>& candies, long long k) {
        int ans = 0; // 初始化答案為零
        // 根據最大的糖果堆數量來決定初始的跳躍大小
        for (int jump = *max_element(candies.begin(), candies.end()); jump > 0; jump /= 2) {
            // 當可以用 ans + jump 分配糖果時，不斷增加 ans
            while (check(candies, k, ans + jump)) {
                ans += jump;
            }
        }
        return ans; // 返回每位小孩可以得到的最大糖果數量
    }
};

Python

class Solution:
    # 函數用來檢查是否能以每個小孩得到正好't'糖果的方式來分配糖果
    def check(self, candies, k, t):
        if t == 0:
            return False  # 若每個小孩沒有糖果，返回False
        for c in candies:
            k -= c // t  # 根據一堆糖果能滿足的小孩數量來減少所需小孩數量
        return k <= 0  # 如果能滿足所有小孩則返回True

    # 函數用來找出每個小孩能獲得的最多糖果數量
    def maximumCandies(self, candies, k):
        ans = 0  # 將答案初始化為零
        # 根據最大的糖果堆來決定初始跳躍大小
        jump = max(candies)
        while jump > 0:
            # 只要能以ans + jump分配糖果，便增加ans
            while self.check(candies, k, ans + jump):
                ans += jump
            jump //= 2
        return ans  # 返回每個小孩能獲得的最多糖果數量

複雜度分析

• 時間複雜度: $O(n \log m)$

  maximumCandies 函數從最大的糖果堆開始，迭代不同的跳躍大小，並在每次迭代中將跳躍大小減半。這個過程本質上是模擬了對每個孩子可以收到的糖果數目的範圍進行二分搜尋。可以給一個孩子的最大糖果數由最大的糖果堆決定，記作 $m = \max(\text{candies})$。因此，二分搜尋運行 $O(\log m)$ 次迭代。

  在二分搜尋的每次迭代中，會呼叫 check 函數，該函數的時間複雜度為 $O(n)$，其中 $n$ 是糖果堆的數量，因為它遍歷糖果陣列以計算分配是否可行。

  綜合以上，總的時間複雜度為 $O(n \log m)$。

• 空間複雜度: $O(1)$

  空間複雜度是常數，$O(1)$，因為演算法僅使用輸入列表和參數之外的固定數量的額外空間。該函數不會分配大小隨輸入增長的額外資料結構。因此，不論輸入大小如何，只使用固定數量的空間。