LeetCode_二分搜索_中等_2594.修车的最少时间

1.题目

给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n² 分钟内修好 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 <= 10⁵
1 <= ranks[i] <= 100
1 <= cars <= 10⁶

2.思路

（1）二分搜索
本题与 875.爱吃香蕉的珂珂 的思路一样，具体代码如下所示。

相关题目：
LeetCode_二分搜索_中等_875.爱吃香蕉的珂珂

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25