【2594. 修车的最少时间】

来源：力扣（LeetCode）

描述：

给你一个整数数组 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 分钟是修理完所有车需要的最少时间。
1
2
3
4
5
6
7
8

示例 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
2
3
4
5
6
7

提示：

• 1 <= ranks.length <= 10⁵
• 1 <= ranks[i] <= 100
• 1 <= cars <= 10⁶

方法：二分查找

思路与算法

题目要求解修理汽车所需的最少时间，故先考虑二分是否可行，若解的值域范围内有单调性，就可以使用二分：

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

因此，存在单调性。我们枚举一个时间 t，那么能力值为 r 的工人可以修完 ⌊tr⌋ 辆汽车。若所有工人可以修完的汽车数量之和大于等于 cars，那么调整右边界为 t，否则调整左边界为 t + 1 。

二分的上界可以取正无穷，也可以取任意一个工人修完所有车辆所需要的时间。

代码：

class Solution {
public:
    using ll = long long;
    long long repairCars(vector<int>& ranks, int cars) {
        ll l = 1, r = 1ll * ranks[0] * cars * cars;
        auto check = [&](ll m) {
            ll cnt = 0;
            for (auto x : ranks) {
                cnt += sqrt(m / x);
            }
            return cnt >= cars;
        };
        while (l < r) {
            ll m = l + r >> 1;
            if (check(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间 96ms 击败 56.17%使用 C++ 的用户
内存 51.20MB 击败 68.09%使用 C++ 的用户
复杂度分析

• 时间复杂度：O(nlog⁡(L))，其中 n 为 ranks 的长度，L 为二分的上界。
• 空间复杂度：O(1)。过程中仅用到常数个变量。
  author：力扣官方题解