2594. 修車的最少時間

題意

• 給定每個師傅修車的時間和需要修的車輛總數(shù)，計算修理所有汽車需要的最少時間。
• 師傅可以同時修車。

解法 二分

看到題目沒有任何頭緒，直接查看題解。

至于為什么用二分做呢，討論區(qū)有個友友這么說到：

對于修理時間 $t$ 來說：

• 若 $t$ 時間內(nèi)可以修理完所有車，則大于等于 $t$ 時間都可以修理完車；
• 若 $t$時間內(nèi)不能修理完所有車，則小于等于 $t$ 時間也不能修理完車；

存在單調(diào)性。因此，假設(shè)最少需要 $time$ 時間，那么我們要找的就是第一個大于等于 $time$ 的時間 $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的數(shù)的位置 
{
	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的數(shù)的位置 
{
	int mid;
	while(left<=right)
	{
		mid=(left+right)/2;
		if(a[mid]>=x)
			right=mid-1;
		else
			left=mid+1;
	}
	return left;
}

復(fù)雜度

時間復(fù)雜度：O($ranks.size()?(\log max(rank?cars?cars))$ )，每一次二分都要遍歷 ranks 數(shù)組計算可修理最大車輛數(shù)。
空間復(fù)雜度：O(1)，常數(shù)個變量。文章來源地址http://www.zghlxwxcb.cn/news/detail-706256.html

到了這里，關(guān)于【LeetCode - 每日一題】2594. 修車的最少時間（23.09.07）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！