LeetCode每日一题(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.

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 <= 8
• 1 <= cookies[i] <= 105
• 2 <= k <= cookies.length

---

站在饼干的角度来看， 每一袋饼干必定要属于某一个孩子， 我们把每种分配情况都枚举出来取最小的最大不公平度。

note: 切身体会到内存分配不仅耗内存空间，也耗时间(貌似是废话，但实测时间消耗确实有点大)，同样的方法，我采用的办法是把当前的状态数组拷贝一份新的然后修改传入下一层， 得到的结果就是超时， 但是用他们说的 backtracking 的方法，传递引用就可以顺利通过

---

impl Solution {
    
    fn backtracking(cookies: &Vec<i32>, k: i32, i: usize, stat: &mut Vec<i32>) -> i32 {
    
        if i == cookies.len() {
    
            return *stat.iter().max().unwrap();
        }
        let mut ans = i32::MAX;
        for n in 0..k as usize {
    
            stat[n] += cookies[i];
            ans = ans.min(Solution::backtracking(cookies, k, i + 1, stat));
            stat[n] -= cookies[i];
        }
        ans
    }
    pub fn distribute_cookies(cookies: Vec<i32>, k: i32) -> i32 {
    
        Solution::backtracking(&cookies, k, 0, &mut vec![0; k as usize])
    }
}