题解 | #牛牛分蛋糕#

题目：
牛牛今天家里要来客人，所以牛牛今天特意做了他最拿手的两种蛋糕，但是他是一个有洁癖的人，所以他在分蛋糕时，有如下几个原则：
1.他不希望一个盘子里出现两种蛋糕
2.他希望每个盘子中都有蛋糕
3.他想让装有最少蛋糕数量的盘子中装有的蛋糕数量尽可能多
方法一：暴力解法
假设有i个盘子用来放a蛋糕，则用来放b蛋糕的盘子数量为n-i，枚举i从1到n-1，蛋糕尽可能平均地分配到每个盘子中，则在放a蛋糕的每个盘子里至少有a/i个蛋糕，放b蛋糕的每个盘子里至少有b/(n-i)个蛋糕，则每轮循环里取，所有最小值中的最大值即为结果

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 处理函数，返回在所有分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量
     * @param n int整型 n个盘子
     * @param a int整型 a蛋糕数量
     * @param b int整型 b蛋糕数量
     * @return int整型
     */
    public int splitCake (int n, int a, int b) {
        // write code here
        if(n==a+b)return 1;//总数等于盘子数则每个盘子放一个蛋糕
        int res=0;
        for(int i=1;i<n;i++){//枚举第一种蛋糕需要的盘子数
            int temp1=a/i;//平均每个盘子放好
            if(n-i>b)continue;
            int temp2=b/(n-i);//第二种蛋糕需要的盘子数为n-i
            res=Math.max(res,Math.min(temp1,temp2));//取每一轮结果的最大值
        }
        return res;
    }
}

复杂度：
时间复杂度：,枚举n次
空间复杂度：,额外变量的空间复杂度为常数级
方法二：二分法
总的蛋糕数在1到a+b之间，则将这些蛋糕均分到n个盘子里，我们可以采用二分的思想：
每次取中间值为均分到每个盘子里的蛋糕数，算出装a蛋糕的盘子数量和装b蛋糕的盘子数量，如果所需盘子数量小于所拥有的盘子数量，说明盘子有剩余，则可以减小均分到每个盘子里的蛋糕数，则向左部分查找，否则，盘子数量不足，需要增大均分到每个盘子里的蛋糕数，则向右部分查找

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 处理函数，返回在所有分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量
     * @param n int整型 n个盘子
     * @param a int整型 a蛋糕数量
     * @param b int整型 b蛋糕数量
     * @return int整型
     */
    public int splitCake (int n, int a, int b) {
        // write code here
        if(n==a+b)return 1;//总数等于盘子数则每个盘子放一个蛋糕
        int l=1,r=a+b;//r为最多蛋糕数
        int res=1;
        while(l<=r){
            int mid=l+(r-l)/2;//假设均分到每个盘子里的蛋糕数量为mid
            int temp=a/mid+b/mid;//所需盘子数
            if(temp>=n){//蛋糕所需盘子数量大于等于所拥有的盘子数,扩大每个盘子平均的蛋糕数
                l=mid+1;
                res=mid;
            }
            else
                r=mid-1;//否则减小每个盘子平均的蛋糕数
        }
        return res;
    }
}

复杂度：
时间复杂度： ,二分查找区间为1到
空间复杂度：,额外变量的空间复杂度为常数级