Readme

2305.Fair-Distribution-of-Cookies

解法1：常规dfs，遍历cookie

通过DFS遍历所有的分配方案。dfs的每一层处理一块cookie，分支考察分配给每个人的方案。总的时间复杂度就是o(k^N).

解法2：二分+dfs，遍历cookie

我们先二分搜索猜测一个答案t，然后用dfs来寻找是否存在一种分配方案，使得每个人能分到的饼干数量不超过t。最终二分逼近的答案就是所求的最优解。

dfs的原理同解法1. 此时，我们可以有很多剪枝策略：

1. 发现任何一个人的饼干总数已经大于t，就返回false
2. 将cookies从大到小排列，尽早排除那些容易溢出的分支。
3. 如果某块饼干打算分发给某个没有得到饼干的人，那么就不需要平行地尝试分给其他没有得到饼干的人。

解法3：二分+dfs，遍历人

dfs的原理正好相反：每一层处理一个人，对于该人的饼干选配方案就是当前剩余饼干的子集。显然我们可以通过遍历子集的技巧，进行dfs的分支搜索。

同样，如果遍历子集时，发现某种分配方案会导致个人的饼干总数已经大于t，就终止这个探索。