Medium

题目描述

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

解题思路

这是一道典型的二分查找答案题。我们需要找到修理所有汽车的最小时间。

核心思路：

  1. 观察规律：机械工能力值为 r，修理 n 辆车需要 r * n² 分钟。反过来，在给定时间 t 内，能力值为 r 的机械工最多可以修理 ⌊√(t/r)⌋ 辆车。

  2. 二分查找：答案具有单调性 - 如果时间 t 能修完所有车，那么任何大于 t 的时间也能修完。因此可以用二分查找最小的可行时间。

  3. 判断可行性：对于给定时间 mid，计算所有机械工在该时间内最多能修理的汽车总数。如果总数 ≥ cars，说明时间足够。

  4. 边界确定：

    • 左边界：0
    • 右边界：最差情况下，能力最低的机械工修理所有车的时间，即 min_rank * cars²

算法步骤：

  1. 二分查找时间区间 [0, min_rank * cars²]
  2. 对于中间值 mid，检查所有机械工在时间 mid 内能修理的汽车总数
  3. 根据总数与 cars 的比较调整查找区间
  4. 返回找到的最小可行时间

推荐解法：二分查找 + 数学计算

代码实现

class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        long long left = 0, right = (long long)(*min_element(ranks.begin(), ranks.end())) * cars * cars;
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            long long totalCars = 0;
            
            for (int rank : ranks) {
                totalCars += (long long)sqrt(mid / rank);
            }
            
            if (totalCars >= cars) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        left, right = 0, min(ranks) * cars * cars
        
        while left < right:
            mid = (left + right) // 2
            total_cars = 0
            
            for rank in ranks:
                total_cars += int((mid // rank) ** 0.5)
            
            if total_cars >= cars:
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public long RepairCars(int[] ranks, int cars) {
        long left = 0, right = (long)ranks.Min() * cars * cars;
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            long totalCars = 0;
            
            foreach (int rank in ranks) {
                totalCars += (long)Math.Sqrt(mid / rank);
            }
            
            if (totalCars >= cars) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

var repairCars = function(ranks, cars) {
    let left = 0, right = Math.min(...ranks) * cars * cars;
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let totalCars = 0;
        
        for (let rank of ranks) {
            totalCars += Math.floor(Math.sqrt(mid / rank));
        }
        
        if (totalCars >= cars) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log(min_rank × cars²))n 为机械工数量，二分查找需要 log(右边界) 次迭代，每次需要遍历所有机械工
空间复杂度O(1)只使用常数级额外空间

相关题目