【回溯】公平分发饼干

公平分发饼干

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

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

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

• 2 <= cookies.length <= 8
• 1 <= cookies[i] <= 105
• 2 <= k <= cookies.length

回溯

“把一个集合划分成Ｋ组，使得每组的和的最大值最小”应该只能用回溯才能得到正确答案！贪心一定是错的！

回溯的写法并不难，记录当前路径的最大值即可，抵达叶节点时再取极小。

class Solution {
public:
    int distributeCookies(vector<int>& cookies, int k) {
        int n = cookies.size();
        sort(cookies.begin(), cookies.end(), greater<int>());
        // n^k
        int ans = INT_MAX;
        vector<int> v(k, 0);
        function<void(int, int)> dfs = [&](int i, int mx) {
            // exit dfs
            if (i >= n) {
                ans = min(ans, mx);
                return;
            }
            // choose each group
            for (int j = 0; j < k; j++) {
                v[j] += cookies[i];
                dfs(i + 1, max(mx, v[j]));
                v[j] -= cookies[i];
            }
        };
        dfs(0, 0);
        return ans;
    }
};

二分加速回溯

注意到这个题目的答案也具有单调性，故可以用二分法寻找边界。然而判断函数还是需要回溯才能得到正确答案。

class Solution {
public:

    int distributeCookies(vector<int>& cookies, int k) {
        // binary search, n^k logC
        int n = cookies.size();
        sort(cookies.begin(), cookies.end(), greater<int>());
        // n^k
        auto test = [&](int m) {
            vector<int> v(k, 0);
            bool flag = false;
            function<void(int)> dfs = [&](int i) {
                if (flag) return;
                if (i >= n) {
                    for (int j = 0; j < k; j++) {
                        if (v[j] > m) {
                            flag = false;
                            return;
                        }
                    }
                    flag = true;
                    return;
                }
                for (int j = 0; j < k; j++) {
                    // important pruning!
                    if (v[j] + cookies[i] > m) continue;
                    v[j] += cookies[i];
                    dfs(i + 1);
                    v[j] -= cookies[i];
                }
            };
            dfs(0);
            return flag;
        };
        // search for the left border
        int l = 1, r = 1e9 + 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (test(m)) r = m - 1;
            else l = m + 1;
        }
        return l;
    }
};