南昌网站开发技术,朋友圈营销广告,卖网站赚钱,造作网站模版目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
题目给我们一个数值#xff0c;数组里每个元素表示一个老师傅#xff0c;老师傅修车花费的时间等于数值乘上车辆数的平方。
问我们修理…目录
题目
示例
分析
代码 题目 示例 分析
题目给我们一个数值数组里每个元素表示一个老师傅老师傅修车花费的时间等于数值乘上车辆数的平方。
问我们修理一些车最少花费的时间是多少。
咋一看毫无头绪我们该如何入手这种题目呢
首先多个师傅可以同时工作并且每个师傅的工作时间是不一样的也就是说我们无法通过修车数去枚举模拟花费时间那么我们可以反过来倒推用花费时间去枚举模拟修车数量。
计算公式题目已经给出只要我们拥有花费时间就可以计算出每个师傅在这个时间里可以修的车数量。 知道了可以通过时间算数量接着我们再确定时间的范围这时候我们就需要看看测试用例的范围了。 我们按照最极端的情况去计算如果师傅就一人并且数值为100而且车的数量是10的六次方这是最极端的情况了这时候花费的时间就是100乘上10的六次方的平方也就是10的十四次方。
如果师傅最多是一万人并且数值都为1而车的数量只有1那么花费的时间就是1。
范围确定下来了就是 [ 1 , 10的十四次方 ]
如果我们需要一个个去遍历所有可能是答案的时间的话那么运行时间是非常恐怖的因此我们需要用到一点小技巧去减少遍历次数比较容易想到的办法就是二分查找法有了范围的左右区间我们就可以使用二分查找法去寻找了每次我们都取范围的中间数去看看用这么多的时间可以修多少辆车如果比我们需要修的车更多那么我们就收缩右边界反之收缩左边界直到确定到答案即可。
这道题和LeetCode75系列的第五十六题很类似可以说是思路基本一致感兴趣的小伙伴也可以去试着把那一题也去做一下过几天我就会把那题的题解也发出来。
代码
class Solution {
public:bool ok(vectorint ranks,int cars,long long time){long long repair0;for(int rank:ranks){repairstatic_castlong long(sqrt(time/rank)); //计算time的时间内可以修理多少车}return repaircars;}long long repairCars(vectorint ranks, int cars) {long long l1,rLLONG_MAX; //左闭右开,r最大为pow(10,662);while(lr){long long midl(r-l)/2; //防止数值溢出的写法,等于(lr)/2if(ok(ranks,cars,mid)) rmid; //如果修的车比需要的多,那么缩小右边界else lmid1; //如果修的车比需要的少,那么缩小左边界}return l;}
};
