修车的最少时间

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

分钟是修理完所有车需要的最少时间。

示例 2：

输入：ranks = [5,1,8], cars = 6
输出：16
解释：

第一位机械工修 1 辆车，需要 5 1 1 = 5 分钟。
第二位机械工修 4 辆车，需要 1 4 4 = 16 分钟。
第三位机械工修 1 辆车，需要 8 1 1 = 8 分钟。

分钟时修理完所有车需要的最少时间。

提示：

1 <= ranks.length <= 105
1 <= ranks[i] <= 100
1 <= cars <= 106

根据题解的思路
由于无法判断每一个修车师傅修的具体数量，但是可以假设时间为t
则每个师傅修车的数量为sqrt(t/r)，这个函数的自变量为t，故函数为单调递增的
将每一个修车师傅的数量加上大于等于cars，那么这个时间就是ok的

采用二分法

先写一个check()函数

 private boolean check(int[] ranks,long m,long cars){
        long x=0;//用来求和
        for(int i=0;i<ranks.length;i++)
        {
            x+=Math.sqrt(m/ranks[i]);//求在当前t下，每一个师傅的修车数，并叠加
        }
        return x>=cars;//是否总数大于cars
    }

再采用二分

public long repairCars(int[] ranks, int cars) {
        long l=0;
        long r=1l*ranks[0]*cars*cars;//这是假设的最大时间，可以换成rank[rank.length-1]*cars*cars;
        while(l<r){
            long m=l+r>>1;//取中间的时间
            if(check(ranks,m,cars)){
                r=m;//如果满足check函数，则说明右侧所有时间都可以满足，那我们就需要把中间点向左侧移动
            }else{
                l=m+1;//同理
            }
            
        }
        return l;
    }

完整代码

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long l=0;
        long r=1l*ranks[0]*cars*cars;//这是假设的最大时间，可以换成rank[rank.length-1]*cars*cars;
        while(l<r){
            long m=l+r>>1;//取中间的时间
            if(check(ranks,m,cars)){
                r=m;//如果满足check函数，则说明右侧所有时间都可以满足，那我们就需要把中间点向左侧移动
            }else{
                l=m+1;//同理
            }
            
        }
        return l;
    }

    private boolean check(int[] ranks,long m,long cars){
        long x=0;//用来求和
        for(int i=0;i<ranks.length;i++)
        {
            x+=Math.sqrt(m/ranks[i]);//求在当前t下，每一个师傅的修车数，并叠加
        }
        return x>=cars;//是否总数大于cars
    }
}

评论 (0)