描述

题目描述

牛牛今天家里要来客人，所以牛牛今天特意做了他最拿手的两种蛋糕，但是他是一个有洁癖的人，所以他在分蛋糕时，有如下几个原则：
1.他不希望一个盘子里出现两种蛋糕
2.他希望每个盘子中都有蛋糕
3.他想让装有最少蛋糕数量的盘子中装有的蛋糕数量尽可能多

示例1

输入：
5,2,3
返回值：
1

备注

n,a,b(1 ≤ a, b ≤ 105, 2 ≤ n ≤ a + b)
第一个参数代表盘子的数量
第二个参数代表第一种蛋糕的数量
第三个参数代表第二种蛋糕的数量。
程序应返回：在所有分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量。

根据题目内容可知：想要求将蛋糕按规则分盘后，根据规则可以分为m种，每一种分发中最小盘的数量设为Min_i(1<=i<=n),比较所有的Min_i返回其中的最大值。

题解

解题思路

方法一

根据题意可以考虑暴力法将全部的方案列出来并找出所有的Min_i，选择其中的最大值返回。
设置最大的Min_i为Max,第一种蛋糕需要i个盘子，第二种蛋糕则为（n-i）个盘子（1<=i<n）。

原则转化

1.他不希望一个盘子里出现两种蛋糕（第一种蛋糕需要i个盘子，第二种蛋糕则为（n-i）个盘子（1<=i<n））
2.他希望每个盘子中都有蛋糕（Max>=1,并且a/i>=1和b/(n-1)>=1）
3.他想让装有最少蛋糕数量的盘子中装有的蛋糕数量尽可能多（循环求出每种方案的最小盘的蛋糕数量与Max做比较，取大值赋值给Max）
代码如下：

 int splitCake(int n, int a, int b) {
        // write code here
        int max=1;//根据题意可知任何种方案都必须保证每一个盘子中至少有一个
        for (int i = 1; i < n; i++) {
            // a/i代表第一种蛋糕的最小盘的数量，b/(n-i)代表第二种蛋糕的最小盘的数量。
            if(a/i>0&&b/(n-i)>0){
                int min=Math.min(a/i,b/(n-i));
                max=Math.max(max,min);
            }
        }
        return max;
    }

时间复杂度：O(n)
空间复杂度：O(1)

方法二

可以考虑通过二分法来将时间复杂度降为O(loga)。
推导过程：一共有两种蛋糕，有题意可知Max的值的范围为(1<=Max<=(a和b两个数中最小的一个))。
如何能保证方案中最少的盘里的蛋糕要比其它方案的最少盘中的蛋糕大，所有的蛋糕尽量平均分配的时候，最小盘里面的蛋糕是比其他方案的最小盘里的蛋糕都要大。
如果a/Max+b/Max<n,就代表有空盘子，不符合题目要求。
所以a/Max+b/Max>=n,才能保证这个方案可行。而什么时候Max是最大的，当a/Max+b/Max趋近于n的时候（趋近于n时，代表着方案最接***均分配），此时Max最大即为所求。

    int splitCake(int n, int a, int b) {
        // write code here
        if(n==a+b){
            return 1;
        }
        if(a>b){
            int temp=a;
            a=b;
            b=temp;
        }
        int left=1;
        int right=a;
        while(left<=right){
            int mid=left+(right-left)/2;
            int k=a/mid+b/mid;
            if(k<n){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        return left-1;
    }

时间复杂度：O(logx)(x为两种蛋糕a和b中最小的值)
空间复杂度：O(1)
可是运行的时候你会发现暴力法的运行时间要快于二分法的运行时间。...(*￣０￣)ノ

总结：我要牛牛( ఠൠఠ )ﾉ，我要牛牛( ¯(∞)¯ )，我要可爱的牛牛(●'◡'●)