【LeetCode - 每日一题】2594. 修车的最少时间（23.09.07）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode - 每日一题】2594. 修车的最少时间（23.09.07）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2594. 修车的最少时间

题意

给定每个师傅修车的时间和需要修的车辆总数，计算修理所有汽车需要的最少时间。
师傅可以同时修车。

解法二分

看到题目没有任何头绪，直接查看题解。

至于为什么用二分做呢，讨论区有个友友这么说到：
【LeetCode - 每日一题】2594. 修车的最少时间（23.09.07）,c++,每日一题,leetcode,leetcode,c++,每日一题

对于修理时间 $t$ 来说：

若 $t$ 时间内可以修理完所有车，则大于等于 $t$ 时间都可以修理完车；
若 $t$ 时间内不能修理完所有车，则小于等于 $t$ 时间也不能修理完车；

存在单调性。因此，假设最少需要 $t im e$ 时间，那么我们要找的就是第一个大于等于 $t im e$ 的时间 $t$ 。

所以可以直接套板子：

class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        long long maxTime = (long long)*max_element(ranks.begin(), ranks.end()) * cars * cars;

        long long left = 0, right = maxTime, middle;
        
        long long maxCar = 0;
        while(left < right)
        {
            long long middle = (left +right) / 2;
            maxCar = 0;
            for(auto rank :ranks)
            {
                maxCar += sqrt(middle / rank);  
            }
            // cout << left << " " << right << " " << middle << " " << maxCar << endl;
            
            if(maxCar < cars)
            {
                left = middle + 1;
            }
            else if(maxCar >= cars)
            {

                right = middle;
            }
        }
        return left;
    }
};

另一种写法：

class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        long long maxTime = (long long)*max_element(ranks.begin(), ranks.end()) * cars * cars;

        long long left = 0, right = maxTime, middle;
        
        long long maxCar = 0;
        while(left <= right)
        {
            long long middle = (left +right) / 2;
            maxCar = 0;
            for(auto rank :ranks)
            {
                maxCar += sqrt(middle / rank);  
            }
            // cout << left << " " << right << " " << middle << " " << maxCar << endl;
            
            if(maxCar < cars)
            {
                left = middle + 1;
            }
            else if(maxCar > cars)
            {

                right = middle - 1;
            }
            else if(maxCar == cars)
            {
                right = middle - 1;
            }
        }
        return left;
    }
};

板子：

int lower_bound(int a[],int left,int right,int x) 	//第一个小于等于x的数的位置 
{
	int mid;
	while(left<right)
	{
		mid=(left+right)/2;
		if(a[mid]>=x)
			right=mid;
		else
			left=mid+1;
	}
	return left;
}

int lower_bound(int a[],int left,int right,int x) 	//第一个小于等于x的数的位置 
{
	int mid;
	while(left<=right)
	{
		mid=(left+right)/2;
		if(a[mid]>=x)
			right=mid-1;
		else
			left=mid+1;
	}
	return left;
}