【算法题】2594. 修车的最少时间

2023-04-18  本文已影响0人  程序员小2

题目:

给你一个整数数组 ranks ,表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。

同时给你一个整数 cars ,表示总共需要修理的汽车数目。

请你返回修理所有汽车 最少 需要多少时间。

注意:所有机械工可以同时修理汽车。

示例 1:

输入:ranks = [4,2,3,1], cars = 10
输出:16
解释:

输入:ranks = [5,1,8], cars = 6
输出:16
解释:

提示:

1 <= ranks.length <= 10^5
1 <= ranks[i] <= 100
1 <= cars <= 10^6

java代码:

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;
    }
}
上一篇下一篇

猜你喜欢

热点阅读