CodeStudio Cooking Ninjas问题：二分搜索中sqrt()函数作用解析求助

我正在解决CodeStudio上的Cooking Ninjas问题，已经自行实现了基于二分搜索的可行解法（代码如下），但无法理解参考解法（见下图）中的部分步骤，尤其是其中sqrt()函数在二分搜索中的作用，恳请帮忙解析。

我的实现代码：

bool isPossible(vector<int> &rank, int m, int mid){
    int sumTime = 0;
    int dishCount = 0;
    
    for(int i=0; i<rank.size(); i++){
        
        for(int j=1; j<=m; j++){
            sumTime += j*rank[i];
            if(sumTime <= mid){
                dishCount++;
            }
            if(dishCount == m){
                return true;
            }
        }
        sumTime = 0;
    }
    return false;
}

int minCookTime(vector<int> &rank, int m){

    int s = 0;
    int e = 0;
    
    for(int i=1; i<=m; i++){
        e += i*rank[rank.size()-1];
    }
    
    int mid = s+(e-s)/2;
    int ans = -1;
    
    while(s<=e){
        if(isPossible(rank, m, mid)){
            ans = mid;
            e = mid - 1;
        }
        else{
            s = mid + 1;
        }
        mid = s+(e-s)/2;
    }
    return ans;
}

我的代码可正常运行，但希望理解参考解法的思路，还请协助解答。

参考解法截图：

参考解法核心逻辑解析 #

参考解法中的sqrt()是用来快速计算单个厨师在给定时间mid内最多能做的菜品数量，替代了你代码里的内层循环，大幅优化了时间复杂度。

公式推导过程：

单个厨师等级为r，做第k道菜的累计时间是等差数列求和：r*(1+2+...+k) = r*k*(k+1)/2。我们需要找到最大的整数k，使得这个累计时间不超过mid，即：
r*k*(k+1)/2 ≤ mid

将不等式整理为一元二次方程形式：
k² + k - (2*mid)/r ≤ 0

用求根公式解这个方程的正根：
k = [-1 + sqrt(1 + 4*(2*mid)/r)] / 2

取这个结果的整数部分，就是该厨师在mid时间内能完成的菜品总数，无需像你代码那样循环累加计算。

效率对比：

• 你的代码内层循环逐个累加，isPossible函数的时间复杂度为O(n*m)（n为厨师数，m为菜品数）
• 参考解法用数学公式计算，isPossible函数时间复杂度降至O(n)，在m较大时，整体二分搜索的效率提升非常明显。

二分边界说明：

参考解法中low=0，high=rank.back()*m*(m+1)/2，和你计算上界e的逻辑完全一致，都是取等级最高的厨师单独完成所有菜品的时间作为二分的最大边界，逻辑合理。

内容的提问来源于stack exchange，提问作者Rakesh Kumar Nahak