题目描述：

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

解法一：二分查找

算法思路：

根据题目要求要查找最少时间，如果解在值域范围内存在单调性，就能够使用二分查找：

• 假设 t 分钟内可以将所有汽车都修理完，那么大于等于 t 分钟内都可以将所有汽车修理完。
• 假设 t 分钟内不能够将所有汽车都修理完，那么小于等于 t 分钟内也不能够将所有汽车修理完。

所以存在单调性。

显然任意一人修完所有车的时间都要大于最少的时间，所以我们定义二分查找的左右边界分别为 left = 0，right = ranks[ 0 ] * cars * cars。依次枚举修车时间 mid，每个机械工人可以休息的汽车数量为 sqrt( mid / rank ),

如果修理的汽车数目大于等于 cars，说明修车时间 mid 可行，那么将右边界缩小至 mid，否则将左边界增大至 mid + 1.

最终返回左边界即可。

代码实现：

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long left = 0, right = 1L * ranks[0] * cars * cars;
        while(left < right){
            long mid = (left + right) >> 1;
            long cnt = 0;
            for(int rank : ranks){
                cnt += Math.sqrt(mid / rank);
            }
            if(cnt >= cars){
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

复杂度分析：

时间复杂度： O( n * log( M ))，其中 n 为机械工的数量，M 为二分查找的上界。

空间复杂度： O( 1 )

相关链接

• 2594. 修车的最少时间