LC.P2594[修车的最少时间]

方法一：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public long repairCars(int[] ranks, int cars) {
        long left = 0, right = (long) 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;
    }
}
  • 时间复杂度：$O(nlogM)$，其中$n$为$ranks$的长度，$M$为二分查找的上界
  • 空间复杂度：$O(1)$