每日一题：leetcode 2594 修车的最少时间

给你一个整数数组 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

Related Topics

• 数组
• 二分查找

思路：

一开始我想是贪心算法，将数组按照rank能力进行升序排序，然后通过优先队列去模拟选人的过程，后来发现思路不对。因为没办法判断每个人应该会修理多少辆车，模拟的话数据量过大应该会超时。

后来想，其实每个人的能力rank是固定的，那么不确定就是能修多少车。如果在确定的时间内，每个人能修理的车的数量其实是可以确定的。根据题目给的公式 rank[i] * n * n = time，那么 n = 根号（time / rank[i]）。这样就明确了，我只需要在一个范围里面进行判断最小的time是什么就行了，这个范围就是[1 - x * n * n]，其中x是随便某个人的rank，n是全部汽车数，即就是随便一个人修完全部车的时间。

最终，这个算法其实就是二分答案，初听这个名字有点炫酷，但是其实就是二分查找，在答案范围内进行查询，找到满足条件的最值即可。（一般二分答案都是解决在某个条件内，最大最小的极值问题）

ac code：

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long ans = 1l * ranks[0] * cars * cars;
        long left = 1;
        long right = ans;
        while (left < right) {
            long mid = left + (right - left) / 2; // 防止数据溢出的小技巧
            if (check(ranks, cars, mid)) { // 二分查询
                ans = mid;
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
 
 
    // 判断答案是否满足
    private boolean check(int[] ranks, int cars, long mid) {
        long cnt = 0;
        for (int x : ranks) {
            cnt += (long) Math.sqrt(mid / x);
        }
        return cnt >= cars;
    }
}