README.md

2305. 公平分发饼干

English Version

题目描述

给你一个整数数组 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] <= 105
• 2 <= k <= cookies.length

解法

方法一：DFS + 剪枝

Python3

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        def dfs(u):
            nonlocal ans
            if u == len(cookies):
                ans = min(ans, max(cnt))
                return
            for i in range(k):
                if cnt[i] + cookies[u] < ans:
                    cnt[i] += cookies[u]
                    dfs(u + 1)
                    cnt[i] -= cookies[u]

        ans = inf
        cnt = [0] * k
        dfs(0)
        return ans

Java

class Solution {
    private int[] cookies;
    private int k;
    private int[] cnt;
    private int ans;

    public int distributeCookies(int[] cookies, int k) {
        ans = 0x3f3f3f3f;
        this.cookies = cookies;
        this.k = k;
        this.cnt = new int[k];
        dfs(0);
        return ans;
    }

    private void dfs(int u) {
        if (u == cookies.length) {
            int mx = cnt[0];
            for (int v : cnt) {
                mx = Math.max(mx, v);
            }
            ans = Math.min(ans, mx);
            return;
        }
        for (int i = 0; i < k; ++i) {
            if (cnt[i] + cookies[u] < ans) {
                cnt[i] += cookies[u];
                dfs(u + 1);
                cnt[i] -= cookies[u];
            }
        }
    }
}

C++

class Solution {
public:
    vector<int> cookies;
    vector<int> cnt;
    int k;
    int ans;

    int distributeCookies(vector<int>& cookies, int k) {
        ans = 0x3f3f3f3f;
        this->cookies = cookies;
        this->cnt = vector<int>(k);
        this->k = k;
        dfs(0);
        return ans;
    }

    void dfs(int u) {
        if (u == cookies.size()) {
            ans = min(ans, *max_element(cnt.begin(), cnt.end()));
            return;
        }
        for (int i = 0; i < k; ++i) {
            if (cnt[i] + cookies[u] < ans) {
                cnt[i] += cookies[u];
                dfs(u + 1);
                cnt[i] -= cookies[u];
            }
        }
    }
};

Go

func distributeCookies(cookies []int, k int) int {
	cnt := make([]int, k)
	ans := 0x3f3f3f3f
	var dfs func(int)
	dfs = func(u int) {
		if u == len(cookies) {
			mx := cnt[0]
			for _, v := range cnt {
				mx = max(mx, v)
			}
			ans = min(ans, mx)
			return
		}
		for i := 0; i < k; i++ {
			if cnt[i]+cookies[u] < ans {
				cnt[i] += cookies[u]
				dfs(u + 1)
				cnt[i] -= cookies[u]
			}
		}
	}
	dfs(0)
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

TypeScript

...