2594. 修车的最少时间

题目描述

给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranks_i 是第 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⁶

解法

方法一：二分查找

思考

第 \(i\) 名工人修 \(x\) 辆车耗时 \(r_i x^2\)，工人并行，求修完 \(\textit{cars}\) 辆的最短时间。分配方案很多，时间范围达 \(r\cdot cars^2\)。

时间越长能修的车越多，故对 \(t\) 二分。时刻 \(t\) 时工人 \(r\) 能修 \(\lfloor\sqrt{t/r}\rfloor\) 辆，总和达到 \(\textit{cars}\) 则可行。\(\textit{bisect\_left}\) 给出最小 \(t\)。

我们注意到，修车时间越长，修理的汽车数目也越多。因此，我们可以将修车时间作为二分查找的目标，二分查找修车时间的最小值。

我们定义二分查找的左右边界分别为 \(left=0\), \(right=ranks[0] \times cars \times cars\)。接下来二分枚举修车时间 \(mid\)，每个机械工可以修理的汽车数目为 \(\lfloor \sqrt{\frac{mid}{r}} \rfloor\)，其中 \(\lfloor x \rfloor\) 表示向下取整。如果修理的汽车数目大于等于 \(cars\)，则说明修车时间 \(mid\) 可行，我们将右边界缩小至 \(mid\)，否则将左边界增大至 \(mid+1\)。

最终，我们返回左边界即可。

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

Python3JavaC++GoTypeScript

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        def check(t: int) -> bool:
            return sum(int(sqrt(t // r)) for r in ranks) >= cars

        return bisect_left(range(ranks[0] * cars * cars), True, key=check)

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 r : ranks) {
                cnt += Math.sqrt(mid / r);
            }
            if (cnt >= cars) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

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

func repairCars(ranks []int, cars int) int64 {
    return int64(sort.Search(ranks[0]*cars*cars, func(t int) bool {
        cnt := 0
        for _, r := range ranks {
            cnt += int(math.Sqrt(float64(t / r)))
        }
        return cnt >= cars
    }))
}

function repairCars(ranks: number[], cars: number): number {
    let left = 0;
    let right = ranks[0] * cars * cars;
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        let cnt = 0;
        for (const r of ranks) {
            cnt += Math.floor(Math.sqrt(mid / r));
        }
        if (cnt >= cars) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

2594. 修车的最少时间

题目描述

解法

方法一：二分查找

评论