LeetCode 5289. 公平分发饼干（DFS）

Michael阿明

发布于 2022-06-13 08:18:48

3980

发布于 2022-06-13 08:18:48

文章目录
1. 题目
2. 解题

1. 题目

给你一个整数数组 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 <= 8
1 <= cookies[i] <= 10^5
2 <= k <= cookies.length

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/fair-distribution-of-cookies 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

数据规模很小，深度优先暴力搜索

class Solution {
    int ans = INT_MAX;
public:
    int distributeCookies(vector<int>& cookies, int k) {
        vector<int> num(k, 0);
        dfs(cookies, num, k, 0);
        return ans;
    }
    void dfs(vector<int>& cookies, vector<int>& num, int k, int i)
    {
        if(i == cookies.size())
        {
            ans = min(ans, *max_element(num.begin(), num.end()));
            return;
        }
        for(int j = 0; j < k; ++j)
        {
            num[j] += cookies[i];
            dfs(cookies, num, k, i+1);
            num[j] -= cookies[i];
        }
    }
};

736 ms 6.7 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-06-12，如有侵权请联系 cloudcommunity@tencent.com 删除

https