牛牛分蛋糕题解

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

1. 普通解法
   时间复杂度O(n) 空间复杂度O(1)
   解题思路：
   暴力求解，枚举数量。
   我们假设把 a 个蛋糕平均分到 i 个盘子，b 个蛋糕平均分到 (n - i) 个盘子，可以得到公式为：n = a/i + b/(n-i)，使用循环实现这个思路即可。

   int solve(int n, int a, int b)
   {
    int i, j;
    int avea;
    int aveb;
    int maxx = 0;
    if (a + b == n)
        maxx = 1;
    for (i = 1; i < n; i++)
    {
        avea = a / i;
        aveb = b / (n - i);
        maxx = max(maxx, min(avea, aveb));
    }
    return maxx;
   }

2. 最优解
   时间复杂度O(logn) 空间复杂度O(1)
   解题思路：
   二分法求解，二分盘子的数量，二分法虽然思路简单，但是细节非常魔鬼，需要多加思考，这里只给出迭代的方法，事实上也可以通过递归来实现二分。
   首先确定搜索区间：左边界设置为1(由题意知，数量最少为1)，右边界设置为 (a + b) / n + 1（由题意可知，最大数量不会超过总数/盘子数），注意这个搜索区间为左闭右开，所以二分的时候while条件可以写成(l<r)，当然如果右边界为 (a + b) / n，while条件应该写成（l<=r）。
   二分该搜索区间，要想蛋糕的最小值最大，蛋糕应该均分,所以区间搜索条件为a / mid + b / mid >= n（每个盘子分不少于mid个蛋糕时最多能分得的盘子数），注意返回为l-1。

int solve(int n, int a, int b)
{
    int l = 1, r = (a + b) / n + 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (a / mid + b / mid >= n)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return l - 1;
}