LeetCode每日一题 2594. 修车的最少时间

题目描述

给定一个整数数组 ranks，表示一些机械工的能力值。其中 ranks[i] 是第 i 位机械工的能力值，表示能够在 ranks[i] * n^2 分钟内修好 n 辆车。同时，给定一个整数 cars，表示总共需要修理的汽车数目。要求计算修理所有汽车所需的最少时间。

算法思路

这个问题可以通过二分查找来解决。我们可以使用二分查找来确定一个时间 t，然后检查是否有足够多的机械工能够在时间 t 内修好所有的汽车。具体步骤如下：

1. 初始化左边界 l 为 0 和右边界 r 为一个较大的值，例如 2 * ranks[0] * cars * cars。这是一个初始的搜索范围。

2. 进入二分查找循环，继续查找直到左边界小于右边界。

3. 在每一次循环中，计算中间值 m = (l + r) / 2。

4. 使用 m 和机械工的能力值 ranks 来估算在时间 m 内可以修好多少辆车。遍历 ranks 数组，对于每个能力值 rk，计算 sqrt(m / rk) 并累加到 num 中。这是因为 rk * n^2 表示能够在 rk * n^2 分钟内修好 n 辆车，所以 sqrt(m / rk) 表示在时间 m 内可以修好的车辆数目。

5. 检查 num 是否大于或等于 cars。如果是，则表示在时间 m 内可以修好足够多的汽车，将右边界 r 更新为 m。如果不是，则表示在时间 m 内无法修好足够多的汽车，将左边界 l 更新为 m + 1。

6. 最终返回左边界 l，即为修理所有汽车所需的最少时间。

代码实现

class Solution {
   
public:
    long long repairCars(vector<int>& ranks, int cars) {
   
        long long l = 0, r = 2ll * ranks[0] * cars * cars;
        while (l < r) {
   
            auto m = (l + r) >> 1;
            long long num = 0;
            for (auto rk : ranks) {
   
                num += sqrt(m / rk);
            }
            if (num >= cars) {
   
                r = m;
            } else {
   
                l = m + 1;
            }
        }
        return l;
    }
};

时间复杂度：O(N * log(M))，其中 N 为机械工的数量，M 为搜索的范围，因为我们进行了二分查找。
空间复杂度：O(1)，没有使用额外的数据结构，只使用了常量空间。