2594.修车的最少时间

链接：2594.修车的最少时间
难度：Medium
标签：数组、二分查找
简介：给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。同时给你一个整数 cars ，表示总共需要修理的汽车数目。请你返回修理所有汽车 最少 需要多少时间。

题解 1 - cpp

• 编辑时间：2023-09-07
• 执行用时：112ms
• 内存消耗：51.34MB
• 编程语言：cpp
• 解法介绍：二分答案。

class Solution {
public:
    typedef long long ll;
    ll repairCars(vector<int>& ranks, int cars) {
        auto comp = [&](ll t) {
            ll res = 0;
            for (auto &rank : ranks) {
                res += floor(sqrt(1.0 * t / rank));
            }
            return res;
        };
        ll l = 0, r = LLONG_MAX;
        while (l < r) {
            ll m = (r - l) / 2 + l;
            if (comp(m) >= cars) r = m;
            else l = m + 1;
        }
        return l;
    }
};

题解 2 - python

• 编辑时间：2023-09-07
• 执行用时：1292ms
• 内存消耗：20.16MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        l = 0
        r = 2 ** 63 - 1
        while l < r:
            m = (r - l) // 2 + l
            if sum(floor(sqrt(m / rank)) for rank in ranks) >= cars:
                r = m
            else:
                l = m + 1
        return l

题解 3 - rust

• 编辑时间：2023-09-07
• 执行用时：56ms
• 内存消耗：2.98MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn repair_cars(ranks: Vec<i32>, cars: i32) -> i64 {
        let cars = cars as i64;
        let mut l = 0;
        let mut r = i64::MAX;
        while l < r {
            let m = (r - l) / 2 + l;
            if ranks
                .iter()
                .map(|rank| (m as f64 / *rank as f64).sqrt().floor() as i64)
                .sum::<i64>()
                >= cars
            {
                r = m;
            } else {
                l = m + 1;
            }
        }
        l
    }
}