力扣每日一题---2594. 修车的最少时间

思路

请注意，能力值越低，修车越快，应该翻译成「排名」，排名越靠前，修车越快。）根据题意可以知道r * n * n <= t 的，所以可以利用数学知识进行改变公式，n <= sqrt(t / r)，所以能力值为 r 的工人最多可以修 sqrt(t / r) 辆车 然后累计起来就是总和，所以 t 越大表示能修理的车车越多，所以有了这样的单调性，我们就可以二分答案了。

解题方法

背y总的二分模板

复杂度

• 时间复杂度:

添加时间复杂度, 示例： $O(logn)$

Code

class Solution 
{
    bool check(vector<int>& ranks, int cars,long long mid)
    {    
        long long s = 0;
        for(auto& r : ranks)//遍历数组然后求出所有工人可以修理的车车的总数
            s += sqrt(mid / r);
        return s >= cars;//满足需要修理的车车数量就返回true 否则 false
    }

public:
    long long repairCars(vector<int>& ranks, int cars) 
    {    //下面全是y总的二分模板
        long long left = 0, right = 1e14, mid;
        while(left<right)
        {
            mid = (left + right) / 2;
            if(check(ranks,cars,mid)) right = mid;
            else left = mid+1;
        }
        return right;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23