公平分发饼干

难度: 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⁵
2 <= k <= cookies.length

Submission

运行时间: 45 ms

内存: 16.1 MB

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        cookies.sort()  # 对 cookies进行降序排序，提高效率
        n = len(cookies)
        ans = float("inf")

        def dfs(buckets):
            nonlocal ans
            # 更新答案
            if not cookies:
                ans = min(max(buckets), ans)
                return

            #     # 如果剩下饼干不够分
            # if len(cookies) < sum(1 for i in buckets if not i):
            #     return

            # 如果当前buckets中最大的饼干数大于当前答案
            if max(buckets) >= ans:
                return

            # 尝试把当前饼干给小朋友
            cookie = cookies.pop()
            for i in range(k):
                # 第一块饼干给哪个小朋友结果都一样
                # if len(cookies) == (n-1) and i > 0:
                #     return
                # 回溯
                buckets[i] += cookie
                dfs(buckets)
                buckets[i] -= cookie
            cookies.append(cookie)
            return

        buckets = [0 for _ in range(k)]
        dfs(buckets)
        return ans

Explain

该题解采用了深度优先搜索(DFS)的策略来分配饼干，以找到最小不公平程度。首先，对饼干数组进行排序，以便尝试优先分配较大的饼干，从而可能更快地达到递归终止条件。在DFS函数中，尝试将当前饼干分配给不同的孩子，每次分配后，继续进行深入搜索，直到所有饼干都被分配。搜索过程中，通过比较当前已分配的最大饼干数与全局最小不公平程度，可以提前剪枝，避免无意义的搜索。DFS结束后，返回全局最小不公平程度。

时间复杂度: O(k^n)

空间复杂度: O(n+k)

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        cookies.sort(reverse=True)  # 将 cookies 进行降序排序
        n = len(cookies)
        ans = float('inf')

        def dfs(buckets):
            nonlocal ans
            if not cookies:  # 如果饼干已经全部考虑完
                ans = min(max(buckets), ans)  # 更新最小不公平程度
                return
            if max(buckets) >= ans:  # 剪枝：当前最大饼干数已超过已知最小不公平程度
                return
            cookie = cookies.pop()  # 取出当前要分配的饼干
            for i in range(k):
                buckets[i] += cookie  # 尝试将饼干分配给第i个小朋友
                dfs(buckets)  # 递归继续分配剩余饼干
                buckets[i] -= cookie  # 回溯：撤销当前饼干的分配
            cookies.append(cookie)  # 将饼干放回去，以供下一轮分配
        buckets = [0 for _ in range(k)]  # 初始化每个小朋友的饼干数
        dfs(buckets)  # 开始DFS搜索
        return ans  # 返回最小不公平程度

Explore

在DFS递归过程中，检查`max(buckets) >= ans`的目的是为了提高算法的效率和减少不必要的计算。这个条件用于剪枝，意味着如果当前的最大饼干数已经超过了我们之前找到的最小不公平程度（`ans`），那么继续分配饼干只会使不公平程度更大，因此没有必要继续探索这个分支。这样的剪枝可以显著减少搜索空间，加快搜索速度，避免在已知不能提供更优解的情况下浪费计算资源。

题解通过对每块饼干在DFS中进行循环，考虑每一种可能的分给k个小孩的方式，可以确保所有可能的分配情况都被探索到。对于每块饼干，算法尝试将它分配给每一个小孩（即k种情况），并且这种分配是递归进行的，这意味着每一层递归都会考虑到所有可能的分配方式。由于每次递归都从所有小孩中选择一个来分配当前饼干，这种全面的探索确保了每一种分配组合都能被评估，覆盖了所有的分配情况。

题解中的回溯方法通过在分配饼干给某个小孩后，递归调用完成后撤销该操作，确保状态的正确还原。具体来说，每当一个饼干被分配给一个小孩时，该小孩的饼干数量会增加，进入下一层递归后，递归返回时会将该小孩的饼干数量减去同样的数值（撤销分配）。这样，状态就被还原到了分配该饼干之前的状态，确保了每次递归调用都从同一个状态开始分配不同的饼干或不同的分配方式。这种精确的状态控制是深度优先搜索中回溯步骤的关键，保证了算法的正确性和完整性。