题目

给你一个整数数组 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fair-distribution-of-cookies
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

唉，这个题没做出来就说明最近刷题效果没有之前好了

第一反应是二分，可能是2064. 分配给商店的最多商品的最小值和2187. 完成旅途的最少时间 这类题做多了的原因，二分孩子中拥有最多饼干的最大值（记为mid），然后根据是否可以分给k个孩子来改变二分区间，其实思路完全是可行的，但是比赛时思路有一点偏差：比赛时想的是根据mid求出需要分给多少个孩子（这一点不太好写），相比较之，采用473. 火柴拼正方形的思路更为直接，判断每个孩子最多分mid的情况下，能否分给k个孩子，这就和473基本一样了。代码如代码一所示，dfs中只需要找一种可行的方案，因此和暴力的dfs时间复杂度不一样，不过加入剪枝的回溯也只能给出一个上限的时间，但是经过测试，比暴力回溯要快很多。

翻遍了题解和评论也没有看到二分的思路，因为数据量小，大家都是直接暴力回溯的。我怎么没有想到，陷入二分的陷阱了…但是不加剪枝的暴力会超时，剪枝思路可以看「这里」，见代码二。

代码

代码一 二分

  1. class Solution {
  2.     public int distributeCookies(int[] cookies, int k) {
  3.         int n = cookies.length;
  4.         // 和473一样，降序排列可以减少搜索次数
  5.         Arrays.sort(cookies);
  6.         for (int i = 0; i <= n / 2; i++) {
  7.             int tmp = cookies[i];
  8.             cookies[i] = cookies[n - 1 - i];
  9.             cookies[n - 1 - i] = tmp;
  10.         }
  11.         // 二分下界为零食包的最大值
  12.         int low = Arrays.stream(cookies).max().getAsInt();
  13.         // 上界（无法取到，但不影响结果）为零食包总和，即分给一个孩子
  14.         int high = Arrays.stream(cookies).sum();
  15.         while (low < high) {
  16.             int mid = low + (high - low) / 2;
  17.             int[] num = new int[k];
  18.             // 最多的孩子即使拿mid个饼干，cookies分给k个孩子还是会有剩余饼干分不出去，必须增加这个最大值
  19.             if (!dfs(cookies, mid, k, num, 0)) {
  20.                 low = mid + 1;
  21.             } else {
  22.                 high = mid;
  23.             }
  24.         }
  25.         return low;
  26.     }
  28.     // 判断每个孩子最多分cap个饼干的情况下，能否将cookies分给k个孩子
  29.     private boolean dfs(int[] cookies, int cap, int k, int[] num, int index) {
  30.         boolean ans = false;
  31.         if (index == cookies.length) {
  32.             return true;
  33.         }
  34.         for (int i = 0; i < k; i++) {
  35.             // 这里很关键，找到一种方案即可，可以大大加快时间
  36.             if (ans) {
  37.                break;
  38.             }
  39.             if (num[i] + cookies[index] <= cap) {
  40.                 num[i] += cookies[index];
  41.                 ans |= dfs(cookies, cap, k, num, index + 1);
  42.                 num[i] -= cookies[index];
  43.             }
  44.         }
  45.         return ans;
  46.     }
  47. }

代码二 暴力回溯

  1. class Solution {
  2.     int ans = Integer.MAX_VALUE;
  4.     public int distributeCookies(int[] cookies, int k) {
  5.         int n = cookies.length;
  6.         Arrays.sort(cookies);
  7.         for (int i = 0; i <= n / 2; i++) {
  8.             int tmp = cookies[i];
  9.             cookies[i] = cookies[n - 1 - i];
  10.             cookies[n - 1 - i] = tmp;
  11.         }
  12.         int[] num = new int[k];
  13.         dfs(cookies, k, num, 0);
  14.         return ans;
  15.     }
  17.     private void dfs(int[] cookies, int k, int[] num, int index) {
  18.         if (index == cookies.length) {
  19.             ans = Math.min(ans, Arrays.stream(num).max().getAsInt());
  20.             return;
  21.         }
  22.         int zeroCount = 0;
  23.         for (int count : num) {
  24.             if (count == 0) zeroCount++;
  25.         }
  26.         // 剪枝一:剩余的零食包不够分给还没有饼干的小孩
  27.         if (zeroCount > cookies.length - index) {
  28.             return;
  29.         }
  30.         for (int i = 0; i < k; i++) {
  31.             // 剪枝二:第一个零食包分给哪个孩子都一样，这里分给第一个孩子，树可以减少一层
  32.             if (index == 0 && i > 0) {
  33.                 break;
  34.             }
  35.             // 剪枝三:如果当前孩子饼干数超过ans了，没必要继续了
  36.             if (num[i] + cookies[index] <= ans) {
  37.                 num[i] += cookies[index];
  38.                 dfs(cookies, k, num, index + 1);
  39.                 num[i] -= cookies[index];
  40.             }
  41.         }
  42.     }
  43. }