[LeetCode] Fair Distribution of Cookies

2305. Fair Distribution of Cookies

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
int dp[1<<10][10];
vector<int> comb(int mask, int n) {
vector<int> cand;
for(int i = 0; i < n; i++) {
if (mask & (1 << i)) continue;
cand.push_back(i);
}
vector<int> res;
for(int i = 1; i < (1<<cand.size()); i++) {
int m = 0;
for(int j = 0; j < cand.size(); j++) {
if(i & (1<<j)) {
m |= 1<<(cand[j]);
}
}
res.push_back(m);
}
return res;
}
int helper(int mask, int now, int k, vector<int>& A) {
if(mask == (1<<A.size()) - 1) {
if(now == k) return 0;
return INT_MAX;
}
if(now == k) return INT_MAX;
if(dp[mask][now] != -1) return dp[mask][now];
int& res = dp[mask][now] = INT_MAX;
auto combs = comb(mask, A.size());
for(auto& c : combs) {
int cost = 0;
for(int i = 0; i < A.size(); i++) {
if(c & (1<<i)) cost += A[i];
}
res = min(res, max(cost, helper(mask | c, now + 1, k , A)));
}
return res;
}
public:
int distributeCookies(vector<int>& A, int k) {
memset(dp, -1, sizeof dp);
return helper(0,0,k,A);
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/12/PS/LeetCode/fair-distribution-of-cookies/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.