class Solution {
public:
long long repairCars(vector<int>& ranks, int cars) {
}
};
6325. 修车的最少时间
给你一个整数数组 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原站题解
php 解法, 执行用时: 208 ms, 内存消耗: 31.1 MB, 提交时间: 2023-09-07 07:36:10
class Solution {
/**
* @param Integer[] $ranks
* @param Integer $cars
* @return Integer
*/
function repairCars($ranks, $cars) {
$l=1;
$r=9223372036854775807;
while ($l<$r){
$mid=floor($l+(($r-$l)>>1));
$t=0;
$top=false;
foreach ($ranks as $v){
$t+=floor(sqrt($mid/$v));
if ($t>=$cars){
$top=true;
break;
}
}
if ($top)$r=$mid;
else $l=$mid+1;
}
return intval($l);
}
}
python3 解法, 执行用时: 84 ms, 内存消耗: 19.4 MB, 提交时间: 2023-03-19 22:12:32
class Solution:
def repairCars(self, ranks: List[int], cars: int) -> int:
cnt = Counter(ranks)
s = lambda t: sum(floor(sqrt(t // r)) * c for r, c in cnt.items())
return bisect_left(range(min(cnt) * cars * cars), cars, key=s)
java 解法, 执行用时: 6 ms, 内存消耗: 48.8 MB, 提交时间: 2023-03-19 22:12:19
class Solution {
public long repairCars(int[] ranks, int cars) {
int minR = ranks[0];
var cnt = new int[101];
for (int r : ranks) {
minR = Math.min(minR, r);
++cnt[r];
}
long left = 0, right = (long) minR * cars * cars;
while (left + 1 < right) { // 开区间
long mid = (left + right) / 2, s = 0;
for (int r = minR; r <= 100; ++r)
s += (long) Math.sqrt(mid / r) * cnt[r];
if (s >= cars) right = mid;
else left = mid;
}
return right;
}
}
cpp 解法, 执行用时: 44 ms, 内存消耗: 52.5 MB, 提交时间: 2023-03-19 22:12:08
class Solution {
public:
long long repairCars(vector<int> &ranks, int cars) {
int min_r = ranks[0], cnt[101]{};
for (int r : ranks) {
min_r = min(min_r, r);
++cnt[r];
}
long long left = 0, right = 1LL * min_r * cars * cars;
while (left + 1 < right) { // 开区间
long long mid = (left + right) / 2, s = 0;
for (int r = min_r; r <= 100; ++r)
s += (long long) sqrt(mid / r) * cnt[r];
(s >= cars ? right : left) = mid;
}
return right;
}
};
golang 解法, 执行用时: 36 ms, 内存消耗: 7.7 MB, 提交时间: 2023-03-19 22:11:54
func repairCars(ranks []int, cars int) int64 {
minR := ranks[0]
cnt := [101]int{}
for _, r := range ranks {
if r < minR {
minR = r
}
cnt[r]++
}
return int64(sort.Search(minR*cars*cars, func(t int) bool {
s := 0
for r := minR; r <= 100; r++ {
s += int(math.Sqrt(float64(t/r))) * cnt[r]
}
return s >= cars
}))
}
golang 解法, 执行用时: 60 ms, 内存消耗: 7.7 MB, 提交时间: 2023-03-19 22:11:34
func repairCars(ranks []int, cars int) int64 {
minR := ranks[0]
for _, r := range ranks {
if r < minR {
minR = r
}
}
return int64(sort.Search(minR*cars*cars, func(t int) bool {
s := 0
for _, r := range ranks {
s += int(math.Sqrt(float64(t / r)))
}
return s >= cars
}))
}
cpp 解法, 执行用时: 92 ms, 内存消耗: 52.4 MB, 提交时间: 2023-03-19 22:11:22
class Solution {
public:
long long repairCars(vector<int> &ranks, int cars) {
int min_r = *min_element(ranks.begin(), ranks.end());
long long left = 0, right = 1LL * min_r * cars * cars;
while (left + 1 < right) { // 开区间
long long mid = (left + right) / 2, s = 0;
for (int r : ranks)
s += sqrt(mid / r);
(s >= cars ? right : left) = mid;
}
return right;
}
};
java 解法, 执行用时: 72 ms, 内存消耗: 48.7 MB, 提交时间: 2023-03-19 22:11:10
class Solution {
public long repairCars(int[] ranks, int cars) {
int minR = ranks[0];
for (int r : ranks) minR = Math.min(minR, r);
long left = 0, right = (long) minR * cars * cars;
while (left + 1 < right) { // 开区间
long mid = (left + right) / 2, s = 0;
for (int r : ranks)
s += Math.sqrt(mid / r);
if (s >= cars) right = mid;
else left = mid;
}
return right;
}
}
python3 解法, 执行用时: 956 ms, 内存消耗: 19.3 MB, 提交时间: 2023-03-19 22:10:56
class Solution:
def repairCars(self, ranks: List[int], cars: int) -> int:
s = lambda t: sum(floor(sqrt(t // r)) for r in ranks)
return bisect_left(range(min(ranks) * cars * cars), cars, key=s)