leetcode：5289. 公平分发饼干【看数据范围 + dfs剪枝】

白速龙王的回眸

于 2022-06-12 18:28:14 发布

阅读量206

点赞数 1

分类专栏： leetcode 文章标签：深度优先 leetcode 剪枝

本文链接：https://blog.csdn.net/weixin_40986490/article/details/125248207

版权

leetcode 专栏收录该内容

781 篇文章

订阅专栏

在这里插入图片描述

分析

一开始没看数据范围想用排序加双指针试试完全没有想法
然后数据这么小就可以暴力了
就是dfs+回溯把当前的饼干试试分给每一个小朋友
然后分完之后看看小朋友中的最大值就是最不公平数
然后求一个最小值即可

注意需要剪枝：
如果当前的最大值已经大于记录的最小值就可以剪掉了

ac code

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        n = len(cookies)
        #own = [0] * k
        ans = inf
        
        def dfs(now, own):
            #print(now, own)
            nonlocal ans
            if now == n:
                ans = min(ans, max(own))
                return
            
            if max(own) >= ans:
                return
            
            for i in range(k):
                own[i] += cookies[now]
                dfs(now + 1, own)
                own[i] -= cookies[now]
        
        dfs(0, [0] * k)
        
        return ans