【C++二分查找】2594. 修车的最少时间

本文主要是介绍【C++二分查找】2594. 修车的最少时间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及的基础知识点

C++二分查找

LeetCode2594. 修车的最少时间

给你一个整数数组 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 <= 10⁵
1 <= ranks[i] <= 100
1 <= cars <= 10⁶

C++二分查找

二分查找类型：寻找首端
Check函数的参数范围：[1,10e14]
Check函数：
f(mid,r) = (int)sqrt(mid/rank)
can = $\sum_{i:0}^{n-1}$ f(mid,rank(i))
return can >= cars
由于误差的原因：f(mid)符合时，试试f(mid+1)是否符合。

代码

核心代码

template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist( _Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd( _Pr pr){int leftInclude = m_iMin;int right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {public:long long repairCars(vector<int>& ranks, int cars) {auto f = [&](long long mid, int r) {long long tmp = sqrt(mid / r);if (r * (tmp + 1) * (tmp + 1) <= mid) { return tmp + 1; }return tmp;};auto Check = [&](long long mid) {long long can = 0;for (const auto& r : ranks) {can += f(mid, r);}return can >= cars;};return CBinarySearch<long long>(1, 1e14 + 1).FindFrist(Check);}};

单元测试

vector<int> ranks;int cars;TEST_METHOD(TestMethod1){ranks = { 1,2 }, cars = 1;auto res = Solution().repairCars(ranks, cars);AssertEx(1LL, res);}TEST_METHOD(TestMethod2){ranks = {100 }, cars = 1'000'000;auto res = Solution().repairCars(ranks, cars);AssertEx(100*(long long)cars*cars, res);}TEST_METHOD(TestMethod11){ranks = { 4, 2, 3, 1 }, cars = 10;auto res = Solution().repairCars(ranks, cars);AssertEx(16LL, res);}TEST_METHOD(TestMethod12){ranks = { 5,1,8 }, cars = 6;auto res = Solution().repairCars(ranks, cars);AssertEx(16LL, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功