LeetCode 题解工作台
公平分发饼干
给你一个整数数组 cookies ，其中 cookies[i] 表示在第 i 个零食包中的饼干数量。另给你一个整数 k 表示等待分发零食包的孩子数量， 所有 零食包都需要分发。在同一个零食包中的所有饼干都必须分发给同一个孩子，不能分开。 分发的 不公平程度 定义为单个孩子在分发过程中能够获得饼干的最…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们先对数组 进行降序排序（减少搜索次数），然后创建一个长度为 的数组 ，用于存储每个孩子分到的饼干数量。另外，用变量 维护当前的最小不公平程度，初始化一个很大的值。 接下来，我们从第一个零食包开始，对于当前零食包 ，我们枚举每个孩子 ，如果当前零食包中的饼干 分给孩子 后，使得不公平程度大于等于 ，或者当前孩子已有的饼干数量与前一个孩子相同，那么我们不需要考虑将当前零食包中的饼干分给孩…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 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 <= 81 <= cookies[i] <= 1052 <= k <= cookies.length
解题思路
方法一：回溯 + 剪枝
我们先对数组 进行降序排序（减少搜索次数），然后创建一个长度为 的数组 ，用于存储每个孩子分到的饼干数量。另外，用变量 维护当前的最小不公平程度，初始化一个很大的值。
接下来，我们从第一个零食包开始，对于当前零食包 ，我们枚举每个孩子 ，如果当前零食包中的饼干 分给孩子 后，使得不公平程度大于等于 ，或者当前孩子已有的饼干数量与前一个孩子相同，那么我们不需要考虑将当前零食包中的饼干分给孩子 ，直接跳过（剪枝）。否则，我们将当前零食包中的饼干 分给孩子 ，然后继续考虑下一个零食包。当我们考虑完所有的零食包后，更新 的值，然后回溯到上一个零食包，继续枚举当前零食包中的饼干分给哪个孩子。
最后，我们返回 即可。
class Solution:
def distributeCookies(self, cookies: List[int], k: int) -> int:
def dfs(i):
if i >= len(cookies):
nonlocal ans
ans = max(cnt)
return
for j in range(k):
if cnt[j] + cookies[i] >= ans or (j and cnt[j] == cnt[j - 1]):
continue
cnt[j] += cookies[i]
dfs(i + 1)
cnt[j] -= cookies[i]
ans = inf
cnt = [0] * k
cookies.sort(reverse=True)
dfs(0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(k^n) |
| 空间 | O(k + n) |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates an understanding of dynamic programming and bitmasking techniques.
- question_mark
Candidate applies backtracking effectively to prune non-optimal solutions.
- question_mark
Candidate explores the time complexity of state transitions and optimizes it effectively.
常见陷阱
外企场景- error
Not pruning the search space efficiently, leading to excessive recursion or slow performance.
- error
Failing to consider all possible distributions of cookies due to incomplete state representation.
- error
Misunderstanding the concept of unfairness, which could lead to suboptimal solutions.
进阶变体
外企场景- arrow_right_alt
Extending the problem to more children, where the size of k increases.
- arrow_right_alt
Changing the problem to minimize the total number of cookies given to any single child instead of the maximum unfairness.
- arrow_right_alt
Introducing constraints where children may not receive the same number of bags.