Medium

题目描述

给你一个整数数组 cookies ，其中 cookies[i] 表示在第 i 个零食包中的饼干数量。另给你一个整数 k 表示等待分发零食包的孩子数量，所有零食包都必须分发。在同一个零食包中的所有饼干都必须分发给同一个孩子，不能分开。

分发的 不公平程度 定义为单个孩子在分发中能够获得饼干的最大总数。

返回所有分发的最小不公平程度。

示例 1：

输入：cookies = [8,15,10,20,8], k = 2
输出：31
解释：一种最优的分发是 [8,15,8] 和 [10,20]
- 第 1 个孩子收到 [8,15,8] ，总计 8 + 15 + 8 = 31 个饼干。
- 第 2 个孩子收到 [10,20] ，总计 10 + 20 = 30 个饼干。
分发的不公平程度为 max(31,30) = 31 。
可以证明不存在不公平程度小于 31 的分发。

示例 2：

输入：cookies = [6,1,3,2,2,4,1,2], k = 3
输出：7
解释：一种最优的分发是 [6,1]、[3,2,2] 和 [4,1,2]
- 第 1 个孩子收到 [6,1] ，总计 6 + 1 = 7 个饼干。
- 第 2 个孩子收到 [3,2,2] ，总计 3 + 2 + 2 = 7 个饼干。 
- 第 3 个孩子收到 [4,1,2] ，总计 4 + 1 + 2 = 7 个饼干。
分发的不公平程度为 max(7,7,7) = 7 。
可以证明不存在不公平程度小于 7 的分发。

提示：

  • 2 <= cookies.length <= 8
  • 1 <= cookies[i] <= 10^5
  • 2 <= k <= cookies.length

解题思路

这是一个典型的回溯搜索问题。我们需要将所有饼干包分配给k个孩子，使得最大总数最小。

基本思路： 使用回溯算法枚举所有可能的分配方案。对于每个饼干包，我们尝试将其分配给每个孩子，然后递归处理下一个饼干包。

优化策略：

  1. 剪枝优化：如果当前分配方案的最大值已经超过了已知的最优解，直接剪枝
  2. 空袋优化：如果当前孩子没有饼干，且后续还有空孩子，则跳过给空孩子分配（避免重复计算）
  3. 排序优化：将饼干包按降序排列，优先分配大的饼干包，可以更早触发剪枝

算法步骤：

  1. 初始化k个孩子的饼干总数数组
  2. 对于每个饼干包，尝试分配给每个孩子
  3. 递归处理下一个饼干包
  4. 当所有饼干包都分配完毕时，计算当前方案的不公平程度
  5. 返回所有方案中的最小不公平程度

时间复杂度虽然是指数级，但由于约束条件较小（cookies.length <= 8），实际运行效率可以接受。

代码实现

class Solution {
public:
    int distributeCookies(vector<int>& cookies, int k) {
        sort(cookies.rbegin(), cookies.rend()); // 降序排列，优先分配大的饼干包
        vector<int> children(k, 0);
        int result = INT_MAX;
        backtrack(cookies, 0, children, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& cookies, int index, vector<int>& children, int& result) {
        if (index == cookies.size()) {
            int maxCookies = *max_element(children.begin(), children.end());
            result = min(result, maxCookies);
            return;
        }
        
        // 剪枝：如果当前最大值已经超过已知最优解，直接返回
        int currentMax = *max_element(children.begin(), children.end());
        if (currentMax >= result) return;
        
        for (int i = 0; i < children.size(); i++) {
            // 空袋优化：避免给多个空孩子分配
            if (i > 0 && children[i] == 0 && children[i-1] == 0) continue;
            
            children[i] += cookies[index];
            backtrack(cookies, index + 1, children, result);
            children[i] -= cookies[index];
        }
    }
};

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        cookies.sort(reverse=True)  # 降序排列
        children = [0] * k
        self.result = float('inf')
        
        def backtrack(index):
            if index == len(cookies):
                self.result = min(self.result, max(children))
                return
            
            # 剪枝
            if max(children) >= self.result:
                return
            
            for i in range(k):
                # 空袋优化
                if i > 0 and children[i] == 0 and children[i-1] == 0:
                    continue
                
                children[i] += cookies[index]
                backtrack(index + 1)
                children[i] -= cookies[index]
        
        backtrack(0)
        return self.result

public class Solution {
    private int result = int.MaxValue;
    
    public int DistributeCookies(int[] cookies, int k) {
        Array.Sort(cookies, (a, b) => b.CompareTo(a)); // 降序排列
        int[] children = new int[k];
        Backtrack(cookies, 0, children);
        return result;
    }
    
    private void Backtrack(int[] cookies, int index, int[] children) {
        if (index == cookies.Length) {
            int maxCookies = children.Max();
            result = Math.Min(result, maxCookies);
            return;
        }
        
        // 剪枝
        if (children.Max() >= result) return;
        
        for (int i = 0; i < children.Length; i++) {
            // 空袋优化
            if (i > 0 && children[i] == 0 && children[i-1] == 0) continue;
            
            children[i] += cookies[index];
            Backtrack(cookies, index + 1, children);
            children[i] -= cookies[index];
        }
    }
}

/**
 * @param {number[]} cookies
 * @param {number} k
 * @return {number}
 */
var distributeCookies = function(cookies, k) {
    const children = new Array(k).fill(0);
    let minUnfairness = Infinity;
    
    function backtrack(index) {
        if (index === cookies.length) {
            minUnfairness = Math.min(minUnfairness, Math.max(...children));
            return;
        }
        
        const currentMax = Math.max(...children);
        if (currentMax >= minUnfairness) return;
        
        for (let i = 0; i < k; i++) {
            children[i] += cookies[index];
            backtrack(index + 1);
            children[i] -= cookies[index];
            
            if (children[i] === 0) break;
        }
    }
    
    backtrack(0);
    return minUnfairness;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(k^n) 其中 n 是饼干包数量，k 是孩子数量。最坏情况下需要尝试所有分配方案，但通过剪枝可以大幅减少实际计算量
空间复杂度O(n + k) 递归栈深度为 n，需要 k 大小的数组存储每个孩子的饼干总数

相关题目