原题链接:
https://leetcode.cn/problems/minimum-time-to-repair-cars/description/

解法1: 二分

需要稍微证明一下
由题:
r * $n^2$ <= t -> n <= $\sqrt{t/r}$
n 与 r 为常量 即n越大 那么能修的车就越多 -> 即拥有单调性因此可以对t进行二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/* 
    二分: 上界为能力最低的机械工 单独修完所有车辆的时间
*/
class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        sort(ranks.begin(),ranks.end());
        long long right = 1LL * ranks[0] * cars * cars;
        // 下界为 left =  0  一辆都不修
        long long left = 0;
        while(left + 1< right){
            long long mid =  (left + right) >> 1, s = 0 ;
            for(auto r : ranks){
                s += sqrt(mid / r);
            }
            // 当修 能力最低花 mid 时间修车时
            // 剩余所有修车者可以修完所有车辆
            // -> 证明 分配给mid 的时间太多 可以少一些 减少上界
            if(s >= cars){
                right = mid;
            }else{
                left = mid;
            }
        }

        return right;
    }
};