公平分发饼干 图解题解

不公平程度，为什么只看拿最多的孩子

cookies[i] 是第 i 包的饼干数，所有包要分给 k 个孩子，每包必须整包给同一个人。一种分法的不公平程度＝拿最多的孩子的总数，要在所有分法里把它压到最小。示例 cookies=[8,15,10,20,8]、k 为 2：[20,10] 给一人共 30，[15,8,8] 给另一人共 31，不公平程度 31，已是最小。

kⁿ 条分法，硬试和贪心各卡在哪

每一包都有 k 个去处，n 包连着选就是 kⁿ 条分法，包数一多根本试不完。贪心也靠不住：把包从大到小排、每包发给当前拿最少的孩子，[20,15,10,8,8] 会分成 20+8=28 和 15+10+8=33，得 33；可最优是 31——10 一旦跟着 15 走，后面怎么补都回不到 31。

逐包试发再撤回，回溯怎么把分法数完

回溯就是一条路走到底、不行退一步换条路的穷举法。开 cnt[j] 记孩子 j 当前拿到的总数，处理某一包时轮流试发：cnt[j] 加上这包，用同一套流程接着发下一包（自己套自己，这就是递归），发完回来把这包减掉，换下一个孩子再试。所有包发出去就走完一条分法，用此刻最大的 cnt 更新最优 ans。加了又减的撤回，保证各分支互不串账。

两把剪刀砍掉的分支，最优解为什么漏不掉

剪枝，就是把注定不会更好的分支整支跳过。第一把：cnt[j] 加上这包后不小于 ans 就不发——这条分支的最大值只会更高，绝无机会刷新答案。第二把：孩子 j 和前一个孩子手里一样多就跳过——这包给谁往后完全对称，只试前一个，砍掉的全是重复分法。

把 cookies 从大到小排序也为剪刀服务：大包先发 cnt 涨得快，第一把剪刀更早够到 ans；排序不改答案，只把砍的时机提前。

五包饼干分给两人，31 是怎么搜出来的

排好序是 [20,15,10,8,8]。发第一包 20 时两人都空手，第二把剪刀只放行孩子一。先一路全发给孩子一得 61，ans 记下 61；退一步把最后一包 8 改给孩子二，得 53；再退再换，ans 一路被压成 45、43、35 三个中间值，各是某条更优分法搜到底时较重那人的总数。

走到 20、10 归孩子一（共 30），15、8 归孩子二（共 23）这条：最后一包 8 发孩子一是 38，不小于 35 被剪，改发孩子二得 23+8=31，两人 30 和 31，ans 刷成 31。之后出现两人 28 和 25、只剩一包 8 的局面：发孩子一 36、发孩子二 33，都不小于 31，两边全剪，走不到头。全部试完，最小不公平程度就是 31。

所有包发完直接改 ans，为什么不会把答案改坏

参考代码发完所有包时直接写 ans = max(cnt)，连比较都不做，靠的正是第一把剪刀：每个值塞进 cnt 时都验过，能走到头就说明此刻 max(cnt) 不超过当前 ans，赋值只会把 ans 改小或持平。时间上界 O(kⁿ)（大 O 是衡量规模对计算量放大倍数的记法），空间 O(n+k)。k 等于包数时每人恰好分一包，答案就是最大那包。最大的一包总得有人整包拿走，答案永远不会低于 max(cookies)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int distributeCookies(vector<int>& cookies, int k) {
        sort(cookies.rbegin(), cookies.rend());
        int cnt[k];
        memset(cnt, 0, sizeof cnt);
        int n = cookies.size();
        int ans = 1 << 30;
        function<void(int)> dfs = [&](int i) {
            if (i >= n) {
                ans = *max_element(cnt, cnt + k);
                return;
            }
            for (int j = 0; j < k; ++j) {
                if (cnt[j] + cookies[i] >= ans || (j && cnt[j] == cnt[j - 1])) {
                    continue;
                }
                cnt[j] += cookies[i];
                dfs(i + 1);
                cnt[j] -= cookies[i];
            }
        };
        dfs(0);
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int[] cookies;
    private int[] cnt;
    private int k;
    private int n;
    private int ans = 1 << 30;

    public int distributeCookies(int[] cookies, int k) {
        n = cookies.length;
        cnt = new int[k];
        // 升序排列
        Arrays.sort(cookies);
        this.cookies = cookies;
        this.k = k;
        // 这里搜索顺序是 n-1, n-2,...0
        dfs(n - 1);
        return ans;
    }

    private void dfs(int i) {
        if (i < 0) {
            // ans = Arrays.stream(cnt).max().getAsInt();
            ans = 0;
            for (int v : cnt) {
                ans = Math.max(ans, v);
            }
            return;
        }
        for (int j = 0; j < k; ++j) {
            if (cnt[j] + cookies[i] >= ans || (j > 0 && cnt[j] == cnt[j - 1])) {
                continue;
            }
            cnt[j] += cookies[i];
            dfs(i - 1);
            cnt[j] -= cookies[i];
        }
    }
}