2305. Fair Distribution of Cookies

#DFS

題目

LeetCode Problem

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.

說明

由於直接暴力搜索只需要看 $8^8 = 16777216$ 個狀態，所以直接 DFS 再加上一點剪枝就好。

Tips:

  1. Max Value 可以直接用 max_element(begin, end)。

Code

 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

const int inf = 100000000;

class Solution {
public:
    int distributeCookies(vector<int>& cookies, int k) {
        vector<int> child(k, 0);
        return dfs(cookies, 0, child);
    }

private:
    int dfs(const vector<int>& cookies, int n, vector<int>& child) {
        if (n == cookies.size()) {
            return *max_element(child.begin(), child.end());
        }

        int minMax = inf;
        for (int lc = 0; lc < child.size(); ++lc) {
            if (child[lc] + cookies[n]>= minMax) {
                continue;
            }
            child[lc] += cookies[n];
            minMax = min(minMax, dfs(cookies, n+1, child));
            child[lc] -= cookies[n];
        }

        return minMax;
    }
};