题解 | #牛牛分蛋糕#

题意整理

给定n个盘子以及a、b两种蛋糕，蛋糕各有一定数量。
要求每个盘子都有蛋糕，且只有一种蛋糕。
求蛋糕数最少的盘子最多能分多少蛋糕。

方法一（枚举）

1.解题思路

由于a、b两种蛋糕的盘子数之和固定为n，只要枚举出a蛋糕的盘子数，b蛋糕盘子数也确定了。
然后计算最少a蛋糕数量的最大值，以及最少b蛋糕数量的最大值，取较小的，用计算出的值跟新结果，找到所有满足条件的最大的结果。

2.代码实现

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) {
        //结果变量
        int res=1;
        //i表示装a蛋糕的盘子数
        for(int i=1;i<n;i++){
            //最少数量a蛋糕的最大值
            int diskA=a/i;
            //最少数量b蛋糕的最大值
            int diskB=b/(n-i);
            res=Math.max(res,Math.min(diskA,diskB));
        }

        return res;
    }

}

3.复杂度分析

时间复杂度：循环体总共需执行 $n-1$ 次，所以时间复杂度为 $O(n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。

方法二（二分查找）

1.解题思路

首先确定所求结果可能的最小值和最大值，每个盘子至少装一个蛋糕，所以最小值是1，只有两个盘子的时候，相应装的蛋糕数最多，此时最少的蛋糕数中最多的可能是a，也可能是b，取两者中的较小者。
然后进行二分查找，只要结果能分够n个盘子，则可以继续寻找更大的结果(往右边找)；如果分不够，则必须减小结果的值(往左边找)。
由于要找可行域的右边界，取中值的时候需要上取整，防止死循环。

动图展示：
图片说明

2.代码实现

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) {
        //二分的左右边界
        int l=1;
        int r=Math.min(a,b);

        while(l<r){
            //因为要找可行域的右边界，这里需要上取整，防止死循环
            int mid=l+(r-l+1)/2;
            //校验mid是否可行，如果可行，则寻找更大的mid
            if(check(n,a,b,mid)){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        return l;

    }

    //最少蛋糕数量是mid时，总共可分配的盘子数应大于等于n
    private boolean check(int n, int a, int b,int mid){

        return a/mid+b/mid>=n;
    }
}

3.复杂度分析

时间复杂度：二分查找时，每次缩小一半的范围，需要查找 $log_2min(a,b)$ 次，所以时间复杂度为 $O(log_2min(a,b))$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。