2023-09-07每日一题

一、题目编号

2594. 修车的最少时间

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

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

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

示例 1：

示例 2：

提示：

• 1 <= ranks.length <= 10⁵
• 1 <= ranks[i] <= 100
• 1 <= cars <= 10⁶

四、解题代码

class Solution {
public:using ll = long long;long long repairCars(vector<int>& 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;}
};

五、解题思路

(1) 使用二分搜索