Question

2594. 修车的最少时间

English Version

题目描述

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

解法

方法一：二分查找

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

我们定义二分查找的左右边界分别为 $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$ 为二分查找的上界。

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;
}