未备案网站加速,h5购物网站模板,app的ui设计案例分析,网站都去哪里找题目链接 Leetcode.2594 修车的最少时间 rating : 1915 题目描述
给你一个整数数组 r a n k s ranks ranks #xff0c;表示一些机械工的 能力值 。 r a n k s _ i ranks\_i ranks_i 是第 i i i 位机械工的能力值。能力值为 r r r 的机械工可以在 r ∗ n 2 r * n^2 r∗n2…题目链接 Leetcode.2594 修车的最少时间 rating : 1915 题目描述
给你一个整数数组 r a n k s ranks ranks 表示一些机械工的 能力值 。 r a n k s _ i ranks\_i ranks_i 是第 i i i 位机械工的能力值。能力值为 r r r 的机械工可以在 r ∗ n 2 r * n^2 r∗n2 分钟内修好 n n n 辆车。
同时给你一个整数 c a r s cars 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 ≤ r a n k s . l e n g t h ≤ 1 0 5 1 \leq ranks.length \leq 10^5 1≤ranks.length≤105 1 ≤ r a n k s [ i ] ≤ 100 1 \leq ranks[i] \leq 100 1≤ranks[i]≤100 1 ≤ c a r s ≤ 1 0 6 1 \leq cars \leq 10^6 1≤cars≤106
解法二分
我们定义 c h e c k ( t ) check(t) check(t) 表示能否在 t t t 分钟的时间里修完 n n n 辆车。
如果能在 t t t 分钟之内修完说明 t t t 就是答案之一。
我们就可以使用二分初始 l 0 , r m a x ( r a n k s [ i ] ) × n 2 l 0 , r max(ranks[i]) \times n^2 l0,rmax(ranks[i])×n2。 m i d ( l r ) / 2 mid (l r) / 2 mid(lr)/2。
如果 c h e c k ( m i d ) check(mid) check(mid) 为真说明在 m i d mid mid 分钟内能够修完 n n n 辆车最少需要 m i d mid mid 分钟即 r m i d r mid rmid如果 c h e c k ( m i d ) check(mid) check(mid) 为假说明在 m i d mid mid 分钟内不能够修完 n n n 辆车最少需要 m i d 1 mid 1 mid1 分钟即 l m i d 1 l mid 1 lmid1
最后返回 l l l 或 r r r 都可以。
时间复杂度 O ( n × l o g n ) O(n \times logn) O(n×logn)
C代码
using LL long long;class Solution {
public:long long repairCars(vectorint ranks, int cars) {int n ranks.size();auto check [](LL t) -bool{int m cars;for(auto r:ranks){LL k static_castLL(sqrt(t / r));if(m k) m - k;else{m 0;break;}}return m 0;};LL l 0 , r 1e14;while(l r){LL mid (r - l) / 2 l;if(check(mid)) r mid;else l mid 1;}return l;}
};
