1.题目
给你一个整数数组 ranks ,表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
同时给你一个整数 cars ,表示总共需要修理的汽车数目。请你返回修理所有汽车最少需要多少时间。
注意:所有机械工可以同时修理汽车。
示例 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 <= 105
1 <= ranks[i] <= 100
1 <= cars <= 106
2.思路
(1)二分搜索
本题与 875.爱吃香蕉的珂珂 的思路一样,具体代码如下所示。文章来源:https://www.toymoban.com/news/detail-699968.html
相关题目:
LeetCode_二分搜索_中等_875.爱吃香蕉的珂珂文章来源地址https://www.toymoban.com/news/detail-699968.html
3.代码实现(Java)
//思路1————二分搜索
class Solution {
public long repairCars(int[] ranks, int cars) {
long left = 1;
long right = (long) ranks[0] * cars * cars;
while (left <= right) {
long mid = left + (right - left) / 2;
if (check(ranks, cars, mid) < cars) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
//返回在 m 分钟内,所有机械工最多可以修好的车辆数
public long check(int[] ranks, int cars, long m) {
long cnt = 0;
for (int x : ranks) {
cnt += (long) Math.sqrt(m / x);
}
return cnt;
}
}
到了这里,关于LeetCode_二分搜索_中等_2594.修车的最少时间的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!