【牛客编程巅峰赛S1第4场】牛牛分蛋糕

题目

牛牛有两种蛋糕，他在分蛋糕时，有如下几个原则：

1. 他不希望一个盘子里出现两种蛋糕
2. 他希望每个盘子中都有蛋糕
3. 他想让装有最少蛋糕数量的盘子中装有的蛋糕数量尽可能多

程序应返回：在所有分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量。

解题思路

使用二分法。
假设盘子中最少的蛋糕数是 mid，那么 a 蛋糕所占盘子的数目小于等于 a / mid，b 蛋糕所占盘子的数目小于等于 b / mid。
如果两种蛋糕所占盘子的数目之和小于 n，那么会有盘子中没有蛋糕，令 right = mid - 1。

C++代码

class Solution {
public:
    /**
     * 处理函数，返回在所有分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量
     * @param n int整型 n个盘子
     * @param a int整型 a蛋糕数量
     * @param b int整型 b蛋糕数量
     * @return int整型
     */
    int solve(int n, int a, int b) {
        // write code here
        int left = 1;
        int right = min(a, b);
        int ans = left;
        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;
                ans = mid;
            }
        }
        return ans;
    }
};