2594. 修车的最好时间

题目描述：

给你一个整数数组 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 <= 10^5
• 1 <= ranks[i] <= 100
• 1 <= cars <= 10^6

---

解题分析及思路：

我们可以使用二分查找来确定修理所有汽车所需的最少时间。

二分查找的范围是从1到一个上限，这个上限可以是正无穷，或者任何一个工人修完所有车辆所需要的时间（推荐，可以减少查找次数）。

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

因此，存在单调性。我们枚举一个时间 m，那么能力值为 x 的工人可以修完 Sqrt(m/x) 辆汽车（其中 Sqrt 表示取根号）。

若所有工人可以修完的汽车数量之和大于等于 cars，那么我们将右边界调整为 m；否则，将左边界调整为 m+1。不断迭代二分查找，最终找到修理所有汽车所需的最少时间。

func repairCars(ranks []int, cars int) int64 {
  l, r := 1, ranks[0]*cars*cars

  for l < r {
    m := (l + r) >> 1 // 计算中间值
    cnt := 0

    // 计算在时间 m 内可以修理的汽车数量之和
    for _, x := range ranks {
      cnt += int(math.Sqrt(float64(m / x)))
    }

    if cnt >= cars {
      r = m
    } else {
      l = m + 1
    }
  }
  return int64(l) // 返回最少时间
}

复杂度：

• 时间复杂度：二分查找的时间复杂度为 O(log(N))，其中 N 为 ranks 数组的长度。
• 空间复杂度：O(1)，只使用了有限的额外空间。

执行结果：

• 执行耗时:64 ms,击败了67.86% 的Go用户
• 内存消耗:7.5 MB,击败了60.71% 的Go用户