目錄
2594. 修車的最少時間
題目描述：
實現(xiàn)代碼與解析：
二分
原理思路：
2594. 修車的最少時間
題目描述：
????????給你一個整數(shù)數(shù)組?ranks?，表示一些機械工的?能力值?。ranksi?是第?i?位機械工的能力值。能力值為?r?的機械工可以在?r * n2?分鐘內修好?n?輛車。
同時給你一個整數(shù)?cars?，表示總共需要修理的汽車數(shù)目。
請你返回修理所有汽車?最少?需要多少時間。
注意：所有機械工可以同時修理汽車。????????
示例 1：
輸入：ranks = [4,2,3,1], cars = 10 輸出：16 解釋： - 第一位機械工修 2 輛車，需要 4 * 2 * 2 = 16 分鐘。 - 第二位機械工修 2 輛車，需要 2 * 2 * 2 = 8 分鐘。 - 第三位機械工修 2 輛車，需要 3 * 2 * 2 = 12 分鐘。 - 第四位機械工修 4 輛車，需要 1 * 4 * 4 = 16 分鐘。 16 分鐘是修理完所有車需要的最少時間。
示例 2：
輸入：ranks = [5,1,8], cars = 6 輸出：16 解釋： - 第一位機械工修 1 輛車，需要 5 * 1 * 1 = 5 分鐘。 - 第二位機械工修 4 輛車，需要 1 * 4 * 4 = 16 分鐘。 - 第三位機械工修 1 輛車，需要 8 * 1 * 1 = 8 分鐘。 16 分鐘時修理完所有車需要的最少時間。
提示：
1 <= ranks.length <= 1051 <= ranks[i] <= 1001 <= cars <= 106
實現(xiàn)代碼與解析：
二分
class Solution {
public:
bool check(long long mid, vector<int> ranks, int cars)
{
long long sum = 0;
for (auto t : ranks)
sum += (long long)sqrt(mid / t);
if (sum >= cars) return true;
else return false;
}
long long repairCars(vector<int>& ranks, int cars) {
sort(ranks.begin(), ranks.end());
long long l = 1, r = 1ll * ranks[0] * cars * cars;
while(l < r)
{
long long mid = l + r >> 1;
if (check(mid, ranks, cars)) r = mid;
else l = mid + 1;
}
return l;
}
};原理思路：
? ? ? ? 看是否能用二分，判斷一下值的范圍是否有單調性，大于等于某一時間可以把車都修好，小于某一時間則不能，因此可以用二分。
? ? ? ? 二分直接套板子即可，check就是檢驗一下當前時間能不能把車修完，大于等于車的數(shù)量說明可以修完。文章來源：http://www.zghlxwxcb.cn/news/detail-699902.html
? ? ? ? 記得開 long long ，1ll 的作用是將int臨時轉化為 long long 賦值給左邊的 long long 類型。學到了。文章來源地址http://www.zghlxwxcb.cn/news/detail-699902.html
到了這里，關于LeetCode每日一題：2594. 修車的最少時間（2023.9.7 C++）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
