| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
Medium |
1886 |
Weekly Contest 297 Q3 |
|
You are given an integer array cookies, where cookies[i] denotes the number of cookies in the ith bag. You are also given an integer k that denotes the number of children to distribute all the bags of cookies to. All the cookies in the same bag must go to the same child and cannot be split up.
The unfairness of a distribution is defined as the maximum total cookies obtained by a single child in the distribution.
Return the minimum unfairness of all distributions.
Example 1:
Input: cookies = [8,15,10,20,8], k = 2 Output: 31 Explanation: One optimal distribution is [8,15,8] and [10,20] - The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies. - The 2nd child receives [10,20] which has a total of 10 + 20 = 30 cookies. The unfairness of the distribution is max(31,30) = 31. It can be shown that there is no distribution with an unfairness less than 31.
Example 2:
Input: cookies = [6,1,3,2,2,4,1,2], k = 3 Output: 7 Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2] - The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies. - The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies. - The 3rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies. The unfairness of the distribution is max(7,7,7) = 7. It can be shown that there is no distribution with an unfairness less than 7.
Constraints:
2 <= cookies.length <= 81 <= cookies[i] <= 1052 <= k <= cookies.length
First, we sort the array
Next, we start from the first snack pack. For the current snack pack
Finally, we return
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;
}