西部数码空间可以做会所网站吗,网站系统里不能打印,专业商城网站制作,大连推广网站搭建哪家好文章目录 思路解题方法复杂度Code 思路 请注意#xff0c;能力值越低#xff0c;修车越快#xff0c;应该翻译成「排名」#xff0c;排名越靠前#xff0c;修车越快。#xff09;根据题意可以知道r * n * n t 的#xff0c;所以可以利用数学知识进行改变公式#… 文章目录 思路解题方法复杂度Code 思路 请注意能力值越低修车越快应该翻译成「排名」排名越靠前修车越快。根据题意可以知道r * n * n t 的所以可以利用数学知识进行改变公式n sqrt(t / r)所以能力值为 r 的工人最多可以修 sqrt(t / r) 辆车 然后累计起来就是总和所以 t 越大表示能修理的车车越多所以有了这样的单调性我们就可以二分答案了。 解题方法 背y总的二分模板 复杂度
时间复杂度: 添加时间复杂度, 示例 O ( l o g n ) O(logn) O(logn) Code
class Solution
{bool check(vectorint ranks, int cars,long long mid){ long long s 0;for(auto r : ranks)//遍历数组然后求出所有工人可以修理的车车的总数s sqrt(mid / r);return s cars;//满足需要修理的车车数量就返回true 否则 false}public:long long repairCars(vectorint ranks, int cars) { //下面全是y总的二分模板long long left 0, right 1e14, mid;while(leftright){mid (left right) / 2;if(check(ranks,cars,mid)) right mid;else left mid1;}return right;}
};
