【力扣每日一题】2023.9.7 修车的最少时间

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

题目给我们一个数值，数组里每个元素表示一个老师傅，老师傅修车花费的时间等于数值乘上车辆数的平方。

问我们修理一些车最少花费的时间是多少。

咋一看毫无头绪，我们该如何入手这种题目呢？

首先，多个师傅可以同时工作，并且每个师傅的工作时间是不一样的，也就是说我们无法通过修车数去枚举模拟花费时间，那么我们可以反过来倒推，用花费时间去枚举模拟修车数量。

计算公式题目已经给出，只要我们拥有花费时间，就可以计算出每个师傅在这个时间里可以修的车数量。

知道了可以通过时间算数量，接着我们再确定时间的范围，这时候我们就需要看看测试用例的范围了。

我们按照最极端的情况去计算，如果师傅就一人，并且数值为100，而且车的数量是10的六次方，这是最极端的情况了，这时候花费的时间就是100乘上10的六次方的平方，也就是10的十四次方。

如果师傅最多是一万人，并且数值都为1，而车的数量只有1，那么花费的时间就是1。

范围确定下来了，就是 [ 1 , 10的十四次方 ]

如果我们需要一个个去遍历所有可能是答案的时间的话，那么运行时间是非常恐怖的，因此我们需要用到一点小技巧去减少遍历次数，比较容易想到的办法就是二分查找法，有了范围的左右区间我们就可以使用二分查找法去寻找了，每次我们都取范围的中间数去看看，用这么多的时间可以修多少辆车，如果比我们需要修的车更多，那么我们就收缩右边界，反之收缩左边界，直到确定到答案即可。

这道题和LeetCode75系列的第五十六题很类似，可以说是思路基本一致，感兴趣的小伙伴也可以去试着把那一题也去做一下，过几天我就会把那题的题解也发出来。

代码：

class Solution {
public:
    bool ok(vector<int>& ranks,int cars,long long time){
        long long repair=0;
        for(int& rank:ranks){
            repair+=static_cast<long long>(sqrt(time/rank));    //计算time的时间内可以修理多少车
        }
        return repair>=cars;
    }
    long long repairCars(vector<int>& ranks, int cars) {
        long long l=1,r=LLONG_MAX;          //左闭右开,r最大为pow(10,6+6+2);
        while(l
            long long mid=l+(r-l)/2;        //防止数值溢出的写法,等于(l+r)/2
            if(ok(ranks,cars,mid)) r=mid; //如果修的车比需要的多,那么缩小右边界
            else l=mid+1;                   //如果修的车比需要的少,那么缩小左边界
        }
        return l;
    }
};