修车的最少时间
原创
给你一个整数数组 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 <= 105
1 <= ranksi <= 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
}
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
腾讯云开发者
