LeetCode_回溯_中等_2305.公平分发饼干

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

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

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

示例 1&＃xff1a;
输入&＃xff1a;COOKIEs &＃61; [8, 15, 10, 20, 8], k &＃61; 2
输出&＃xff1a;31
解释&＃xff1a;一种最优方案是 [8, 15, 8] 和 [10, 20] 。

• 第 1 个孩子分到 [8, 15, 8] &＃xff0c;总计 8 &＃43; 15 &＃43; 8 &＃61; 31 块饼干。
• 第 2 个孩子分到 [10, 20] &＃xff0c;总计 10 &＃43; 20 &＃61; 30 块饼干。

分发的不公平程度为 max(31, 30) &＃61; 31 。
可以证明不存在不公平程度小于 31 的分发方案。

示例 2&＃xff1a;
输入&＃xff1a;COOKIEs &＃61; [6, 1, 3, 2, 2, 4, 1, 2], k &＃61; 3
输出&＃xff1a;7
解释&＃xff1a;一种最优方案是 [6, 1]、[3, 2, 2] 和 [4, 1, 2] 。

• 第 1 个孩子分到 [6, 1] &＃xff0c;总计 6 &＃43; 1 &＃61; 7 块饼干。
• 第 2 个孩子分到 [3, 2, 2] &＃xff0c;总计 3 &＃43; 2 &＃43; 2 &＃61; 7 块饼干。
• 第 3 个孩子分到 [4, 1, 2] &＃xff0c;总计 4 &＃43; 1 &＃43; 2 &＃61; 7 块饼干。

分发的不公平程度为 max(7, 7, 7) &＃61; 7 。
可以证明不存在不公平程度小于 7 的分发方案。

提示&＃xff1a;
2 <&＃61; COOKIEs.length <&＃61; 8
1 <&＃61; COOKIEs[i] <&＃61; 10⁵
2 <&＃61; k <&＃61; COOKIEs.length

来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
链接&＃xff1a;https://leetcode.cn/problems/fair-distribution-of-COOKIEs

&＃xff08;1&＃xff09;回溯算法
思路参考该 LeetCode 用户题解。

本题可以看作 698.划分为k个相等的子集 这题的一个变形&＃xff0c;对于集合划分问题来说&＃xff0c;我们可以知道每个集合可容纳的大小&＃xff1b;但是本问题只是让我们尽可能保证均匀划分&＃xff0c;即题目中的分发的最小不公平程度。

相关题目&＃xff1a;
LeetCode_回溯_中等_473.火柴拼正方形
LeetCode_回溯_中等_698.划分为k个相等的子集

//思路1————回溯算法
class Solution {// res 记录所有分发的最小不公平程度&＃xff0c;其初始值为 Integer.MAX_VALUEprivate int res &＃61; Integer.MAX_VALUE;public int distributeCOOKIEs(int[] COOKIEs, int k) {//定义 k 个桶(集合)&＃xff0c;每个桶记录装入当前桶的元素之和int[] buckets &＃61; new int[k];//对数组 COOKIEs 进程降序排序Arrays.sort(COOKIEs);for (int i &＃61; 0, j &＃61; COOKIEs.length - 1; i < j; i&＃43;&＃43;, j--) {//交换 COOKIEs[i] 和 COOKIEs[j]int temp &＃61; COOKIEs[i];COOKIEs[i] &＃61; COOKIEs[j];COOKIEs[j] &＃61; temp;}backtrack(COOKIEs, 0, buckets);return res;}private void backtrack(int[] COOKIEs, int start, int[] buckets) {if (start &＃61;&＃61; COOKIEs.length) {//一次划分中的最大值int maxVal &＃61; Arrays.stream(buckets).max().getAsInt();//更新 resres &＃61; Math.min(res, maxVal);return;}//空桶数量int emptyBuckets &＃61; 0;for (int bucket : buckets) {if (bucket &＃61;&＃61; 0) {emptyBuckets&＃43;&＃43;;}}//剪枝 1if (emptyBuckets > COOKIEs.length - start) {return;}for (int i &＃61; 0; i < buckets.length; i&＃43;&＃43;) {//剪枝 2if (i > 0 && buckets[i] &＃61;&＃61; buckets[i - 1]) {continue;}//剪枝 3if (buckets[i] &＃43; COOKIEs[start] > res) {continue;}buckets[i] &＃43;&＃61; COOKIEs[start];//进入到下一层backtrack(COOKIEs, start &＃43; 1, buckets);buckets[i] -&＃61; COOKIEs[start];}}
}