当前位置：首页 > article >正文

leetcode 2594. 修车的最少时间

article 2025/2/4 17:53:10

题目如下
在这里插入图片描述
数据范围

显然当修一辆车最久的师傅修完cars辆车所用时间大于等于最短时间所以上界定为这个，而我们不好预测最小时间所以下界直接定为1。
故我们使用二分查找来加速枚举修理过程。

通过代码

class Solution {
public:
    bool check(vector<int>& nums,int sum,long long t){
        long long s = 0;
        int n = nums.size();
        for(int i = 0;i < n;i++){
            s += sqrt(t / (long long)nums[i]);
        }
        return s >= sum;
    }
    long long repairCars(vector<int>& ranks, int cars) {
        long long r = (long long)*max_element(ranks.begin(),ranks.end()) * cars * cars,l = 0;
        long long mid;
        while(l < r){
            mid = l + (r - l)/2;
            if(check(ranks,cars,mid)){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
};