| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
1886 |
第 297 场周赛 Q3 |
|
给你一个整数数组 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 <= 81 <= cookies[i] <= 1052 <= k <= cookies.length
我们先对数组
接下来，我们从第一个零食包开始，对于当前零食包
最后，我们返回
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 ansclass 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];
}
}
}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;
}
};func distributeCookies(cookies []int, k int) int {
sort.Sort(sort.Reverse(sort.IntSlice(cookies)))
cnt := make([]int, k)
ans := 1 << 30
var dfs func(int)
dfs = func(i int) {
if i >= len(cookies) {
ans = slices.Max(cnt)
return
}
for 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]
}
}
dfs(0)
return ans
}function distributeCookies(cookies: number[], k: number): number {
const cnt = new Array(k).fill(0);
let ans = 1 << 30;
const dfs = (i: number) => {
if (i >= cookies.length) {
ans = Math.max(...cnt);
return;
}
for (let 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;
}