2305. Fair Distribution of Cookies

题目 2305. Fair Distribution of Cookies

思路分析

思路和前面一样可以二分出cookie

但问题是它现在不是拿连续的了而是可以随意组合

这意味着需要dfs去枚举所有可能数据范围2-8是可行的

先二分猜一个答案再dfs也行

直接dfs也行

代码实现

class Solution {
    static final int INF = 0x3f3f3f3f;

    private boolean check(int[] cookies,int k,int mid){
        int[] children = new int[k];
        return dfs(cookies,cookies.length-1,children,mid);
    }

    private boolean dfs(int[] cookies,int idx,int[] children,int mid){
        if(idx<0)   return true;
        int cookie = cookies[idx];
        for(int i=0;i<children.length;i++){
            if(children[i]+cookie>mid)  continue;
            if(i>0 && children[i]==children[i-1])   continue;
            if(children[i]==0){
                children[i]+=cookie;
                if(dfs(cookies,idx-1,children,mid))  return true;
                children[i]-=cookie;
                return false;
            }
            children[i]+=cookie;
            if(dfs(cookies,idx-1,children,mid))  return true;
            children[i]-=cookie;
        }
        return false;
    }

    public int distributeCookies(int[] cookies, int k) {
        int sumv=0,maxv=-INF;
        for(int cookie:cookies){
            maxv = Math.max(cookie,maxv);
            sumv+=cookie;
        }
        Arrays.sort(cookies);

        int l=maxv,r=sumv;
        while(l<r){
            int mid=l+r>>1;
            if(check(cookies,k,mid)){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        return r;
    }
}

import java.util.Arrays;

class Solution {
    public int distributeCookies(int[] cookies, int k) {
        int sum = 0;
        for (int c : cookies) sum += c;
        
        // 排序优化：从大到小拿饼干，如果大的放不进，剪枝会更快
        Arrays.sort(cookies); 
        // 倒序处理，虽然Java Arrays没有直接降序，我们可以在dfs里倒着遍历
        
        // 二分范围：
        // 下界 l：至少得装下最大的那一袋饼干（因为不能拆分）
        // 上界 r：一个人拿走所有饼干
        int l = cookies[cookies.length - 1]; 
        int r = sum;
        
        while (l < r) {
            int mid = l + r >> 1;
            // check: 尝试用 k 个孩子，每个孩子上限 mid，能不能分完所有 cookies
            if (check(cookies, k, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }

    // 检查函数：能否将所有饼干分给 k 个孩子，且每个人不超过 limit
    private boolean check(int[] cookies, int k, int limit) {
        int[] children = new int[k]; // 记录每个孩子当前拿了多少
        // 从最后一个饼干（最大的）开始分，容易触发剪枝
        return backtrack(cookies, cookies.length - 1, children, limit);
    }

    // 回溯具体逻辑
    private boolean backtrack(int[] cookies, int idx, int[] children, int limit) {
        // Base Case: 所有的饼干都分完了，说明这个 limit 是可行的
        if (idx < 0) return true;
        
        int cookie = cookies[idx]; // 当前要分的饼干
        
        // 尝试把这袋饼干给 k 个孩子中的某一个
        for (int i = 0; i < children.length; i++) {
            // 剪枝1：如果给在这个孩子会导致超标，就跳过
            if (children[i] + cookie > limit) continue;
            
            // 剪枝2（极其重要）：如果当前孩子和前一个孩子拿的饼干一样多，
            // 那么给这一袋饼干给谁都是一样的，前面那个失败了，这个肯定也失败，跳过。
            // 或者是：如果当前孩子是空的，且把饼干给他后最终失败了，
            // 那么给后面任何一个空着的孩子都会失败（因为大家都是空的，等价的）。
            if (i > 0 && children[i] == children[i-1]) continue; 
            // 实际上对于本题二分check，最强剪枝是：如果当前 bucket 为 0 且递归失败，直接 return false
            // 但为了逻辑简单，用上面的去重逻辑也可以，或者用下面的写法：
            if (children[i] == 0) {
                 // 如果这是一个空桶，尝试放入
                 children[i] += cookie;
                 if (backtrack(cookies, idx - 1, children, limit)) return true;
                 children[i] -= cookie;
                 // 关键点：如果给第一个空桶都失败了，给后面的空桶肯定也失败，直接return false
                 return false;
            }

            // 正常回溯逻辑
            children[i] += cookie;
            if (backtrack(cookies, idx - 1, children, limit)) return true;
            children[i] -= cookie; // 回溯
        }
        
        return false;
    }
}

既然 N 只有 8，其实我们根本不需要二分。二分是在“猜”答案，然后去验证。既然验证过程本身就是指数级的，我们不如直接暴力枚举所有分发方案，在这个过程中维护一个全局最小值。

这种写法代码更短，逻辑更直观。

核心思路

维护一个全局变量 ans 记录最小的不公平值。

dfs(index): 决定第 index 袋饼干给哪个孩子。

class Solution {
    static final int INF = 0x3f3f3f3f;
    int ans = INF;

    public int distributeCookies(int[] cookies, int k) {
        int[] children = new int[k];
        dfs(cookies,0,children,k);
        return ans;    
    }

    private void dfs(int[] cookies,int idx,int[] children,int k){
        if(idx == cookies.length){
            int maxCookie=0;
            for(int c:children) maxCookie=Math.max(maxCookie,c);
            ans = Math.min(ans,maxCookie);
            return;
        }

        int cookie = cookies[idx];

        for(int i=0;i<k;i++){
            if(children[i]+cookie>=ans) continue;

            children[i]+=cookie;
            dfs(cookies,idx+1,children,k);
            children[i]-=cookie;
        }
    }
}

剪枝：如果在分发过程中，某个孩子手里的饼干已经超过了当前的 ans，那就没必要继续分了（因为结果肯定比 ans 差）。

class Solution {
    int ans = Integer.MAX_VALUE;

    public int distributeCookies(int[] cookies, int k) {
        // 每个人当前手里的饼干总数
        int[] children = new int[k];
        dfs(cookies, 0, children, k);
        return ans;
    }

    private void dfs(int[] cookies, int idx, int[] children, int k) {
        // 如果所有饼干都分完了
        if (idx == cookies.length) {
            // 算出当前方案的不公平程度（所有孩子里的最大值）
            int maxCookie = 0;
            for (int c : children) maxCookie = Math.max(maxCookie, c);
            // 更新全局最小
            ans = Math.min(ans, maxCookie);
            return;
        }

        int cookie = cookies[idx];
        
        // 尝试把这袋饼干给 k 个孩子中的每一个
        for (int i = 0; i < k; i++) {
            // 剪枝1：如果当前孩子拿完这袋饼干就已经超过了已知的最优解 ans
            // 那这个方案肯定不是最优解，直接剪掉
            if (children[i] + cookie >= ans) continue;
            
            // 剪枝2：空桶优化
            // 如果当前桶是空的，且把饼干给他之后，后面的递归没能找到比 ans 更优的解
            // 那么给后面其他空桶也是没用的（因为空桶是等价的），直接 break
            if (children[i] == 0) {
                children[i] += cookie;
                dfs(cookies, idx + 1, children, k);
                children[i] -= cookie;
                break; // 关键：不需要尝试下一个空桶了
            }

            // 正常回溯
            children[i] += cookie;
            dfs(cookies, idx + 1, children, k);
            children[i] -= cookie;
        }
    }
}

2305. Fair Distribution of Cookies

2305. Fair Distribution of Cookies

题目 2305. Fair Distribution of Cookies

思路分析

代码实现

核心思路

同类题型

视频讲解

💬 评论