【C++二分查找】875. 爱吃香蕉的珂珂

本文涉及的基础知识点

C++二分查找

LeetCode875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
示例 1：
输入：piles = [3,6,7,11], h = 8
输出：4
示例 2：
输入：piles = [30,11,23,4,20], h = 5
输出：30
示例 3：
输入：piles = [30,11,23,4,20], h = 6
输出：23
提示：
1 <= piles.length <= 10⁴
piles.length <= h <= 10⁹
1 <= piles[i] <= 10⁹

C++二分查找

二分查找类型：寻找首端
Check函数的参数范围：[1,10⁹]
Check函数：
吃完所有香蕉需要的小数数<=h
吃完一堆香蕉的用时：piles[i]/mid + (0 != piles[i]%mid)

代码

核心代码

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:int minEatingSpeed(vector<int>& piles, int h) {auto Check = [&](int mid) {long long need = 0;for (const auto& n : piles) {need += n / mid + (0 != n % mid);}return need <= h;};return CBinarySearch<int>(1, 1e9 + 0.5).FindFrist(Check);}};

单元测试

vector<int> piles;int h;TEST_METHOD(TestMethod13){piles = { 3, 6, 7, 11 }, h = 8;auto res = Solution().minEatingSpeed(piles, h);AssertEx(4, res);}TEST_METHOD(TestMethod14){piles = { 30,11,23,4,20 }, h = 5;auto res = Solution().minEatingSpeed(piles, h);AssertEx(30, res);}TEST_METHOD(TestMethod15){piles = { 30,11,23,4,20 }, h = 6;auto res = Solution().minEatingSpeed(piles, h);AssertEx(23, res);}

扩展阅读

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