企业网站管理系统信得过y湖南岚鸿怎么样,旅游网站建设的论文,企业融资计划书,怎么看网站是否备案成功来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给你一个整数数组 ranks #xff0c;表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
同时给你一个整数 cars #xff0c;表示…来源力扣LeetCode
描述
给你一个整数数组 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 1051 ranks[i] 1001 cars 106
方法二分查找
思路与算法
题目要求解修理汽车所需的最少时间故先考虑二分是否可行若解的值域范围内有单调性就可以使用二分
假设 t 分钟内可以将所有汽车都修理完那么大于等于 t 分钟内都可以将所有汽车修理完。假设 t 分钟内不能够将所有汽车都修理完那么小于等于 t 分钟内也不能够将所有汽车修理完。
因此存在单调性。我们枚举一个时间 t那么能力值为 r 的工人可以修完 ⌊tr⌋ 辆汽车。若所有工人可以修完的汽车数量之和大于等于 cars那么调整右边界为 t否则调整左边界为 t 1 。
二分的上界可以取正无穷也可以取任意一个工人修完所有车辆所需要的时间。
代码
class Solution {
public:using ll long long;long long repairCars(vectorint ranks, int cars) {ll l 1, r 1ll * ranks[0] * cars * cars;auto check [](ll m) {ll cnt 0;for (auto x : ranks) {cnt sqrt(m / x);}return cnt cars;};while (l r) {ll m l r 1;if (check(m)) {r m;} else {l m 1;}}return l;}
};时间 96ms 击败 56.17%使用 C 的用户 内存 51.20MB 击败 68.09%使用 C 的用户 复杂度分析 时间复杂度O(nlog(L))其中 n 为 ranks 的长度L 为二分的上界。空间复杂度O(1)。过程中仅用到常数个变量。 author力扣官方题解
