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

超、凢脫俗 2024-03-08 04:28 49阅读 0赞

![在这里插入图片描述][40050d4d27c04c9bb2f96d0d5df0b404.png]

#### 文章目录 ####

*  思路
 *  解题方法
 *  复杂度
 *  Code

## 思路 ##

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

## 解题方法 ##

> 背y总的二分模板

## 复杂度 ##

*  时间复杂度:

> 添加时间复杂度, 示例：  O ( l o g n ) O(logn) 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;
        }
    };

![在这里插入图片描述][240df8d1741e4d4f8e17e0ac0a0e1759.png]

[40050d4d27c04c9bb2f96d0d5df0b404.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/2dfeffdaebc649df9eee2c4409af654c.png
[240df8d1741e4d4f8e17e0ac0a0e1759.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/f579e3f603dc496ba2638d7fed406a68.png