惠州淡水网站建设,中国建筑网官网招聘网,asp.net个人网站空间,开发公司英文文章目录 Tag题目来源题目解读解题思路方法一#xff1a;二分枚举答案 写在最后 Tag
【二分枚举答案】【数组】 题目来源
2594. 修车的最少时间 题目解读
给你一个表示机械工能力的数组 ranks#xff0c;ranks[i] 表示第 i 位机械工可以在 r a n k s [ i ] ∗ n 2 ranks[… 文章目录 Tag题目来源题目解读解题思路方法一二分枚举答案 写在最后 Tag
【二分枚举答案】【数组】 题目来源
2594. 修车的最少时间 题目解读
给你一个表示机械工能力的数组 ranksranks[i] 表示第 i 位机械工可以在 r a n k s [ i ] ∗ n 2 ranks[i] * n ^2 ranks[i]∗n2 分钟内修好 n 辆车。所有的机械工可以同时修理汽车返回修理完所有汽车需要的最少时间。 解题思路
方法一二分枚举答案
如果已知修车的时间为 t t t那么我们可以计算每个人在 t 分钟内可以修好的车辆数。如果一个工人的修车能力为 r则有这样的表达式 r n 2 t rn^2 t rn2t 解得 n t r n \sqrt{\frac{t}{r}} nrt 于是能力值为 r 的工人最多可以修车 ⌊ t r ⌋ \lfloor{\frac{t}{r}}\rfloor ⌊rt⌋ 辆。
累加每个机械工在 t 分钟内的修车数量如果有 ∑ i 0 n − 1 ⌊ t r a n k s [ i ] ⌋ c a r s \sum_{i0}^{n-1}{\lfloor \sqrt{\frac{t}{ranks\left[ i \right]}} \rfloor}cars i0∑n−1⌊ranks[i]t ⌋cars
则说明可以在 t 分钟内修完所有的车。
上式表明t 越大能修好的车子越多。有了这样的单调性我们就可以二分枚举答案了二分的上界为修车最快的人修完所有车子的时间即 m i n ( r a n k s ) ⋅ c a r s 2 min(ranks) \cdot cars^2 min(ranks)⋅cars2。
在具体实现中我们枚举修车的时间 t如果所有机械工在 t 分钟内修完的汽车数量大于等于 cars则调整右边界为 t否则调整左边界为 t1。
实现代码
class Solution {
public:long long repairCars(vectorint ranks, int cars) {int minR *min_element(ranks.begin(), ranks.end());long long left 0, right 1LL * minR * cars * cars;auto check [](long long m) {long long cnt 0;for (int r : ranks) {cnt sqrt(m / r);}return cnt cars;};while (left right) {long long mid left ((right - left) 1);if (check(mid)) {right mid;}else {left mid 1;}}return left;}
};复杂度分析
时间复杂度 O ( n l o g L ) O(nlogL) O(nlogL) n n n 为数组 ranks 的长度 L L L 为二分的上界。
空间复杂度 O ( 1 ) O(1) O(1)因为仅用了常数个变量。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
