2594. 修车的最少时间 (opens new window)

1.二分查找+最大最小问题

本题目关键在于理解题目，如果工人时间是串行的要求出最少时间，那么可以使用先序队列或小顶堆枚举所有车辆，排序规则为全局最小增量，得到的总时长也肯定是最少的。然而本题目工人的时间是并行的，要求给出并行的最少时间，也就是带约束的最大最小值问题，只能枚举修车时间进行求解。

解题思路：二分逼近找到最少时间，能够使用二分是因为对于时间n:

• 如果n不能修完所有的车，那么小于n的时间都不能修完所有的车
• 如果n可以修完所有的车，那么大于n的时间都可以修完所有的车

因此关键在于如果判断在时间n之内是否可以修完所有的车，因为修车过程是并行的，可以枚举所有工人，计算每个工人的修车数然后加起来，得到的总车数如果比cars大则说明在时间n内可以修完。时间复杂度(n*log l)，其中l是枚举的时间上限。

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;
            if(check(ranks,cars,mid)) right=mid;
            else left=mid+1;
        }
        return left;
    }
    public boolean check(int[] ranks, int cars,long num){
        long cnt=0;
        for(int x:ranks){
            cnt+=(long) Math.sqrt(num/x);
        }
        return cnt>=cars;
    }
}