延安做网站的公司电话驻马店网站建设公司

延安做网站的公司电话,驻马店网站建设公司,上海网站制作服务,专业网站美工题目描述珂珂喜欢吃香蕉。这里有 n 堆香蕉#xff0c;第 i 堆中有 piles[i] 根香蕉。警卫已经离开了#xff0c;将在 h 小时后回来。珂珂可以决定她吃香蕉的速度 k #xff08;单位#xff1a;根/小时#xff09;。每个小时#xff0c;她将会选择一堆香蕉#xff0c;从中…题目描述珂珂喜欢吃香蕉。这里有n堆香蕉第i堆中有piles[i]根香蕉。警卫已经离开了将在h小时后回来。珂珂可以决定她吃香蕉的速度k单位根/小时。每个小时她将会选择一堆香蕉从中吃掉k根。如果这堆香蕉少于k根她将吃掉这堆的所有香蕉然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在h小时内吃掉所有香蕉的最小速度kk为整数。示例 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 104piles.length h 1091 piles[i] 109解决方案算法目标找出Koko每小时吃香蕉的最小速度k使得她能在h小时内吃完所有香蕉堆。核心思路确定查找范围速度k在[1, 最大香蕉堆]之间二分查找尝试不同的速度找到满足条件的最小速度验证可行性对每个尝试的速度计算吃完所有香蕉需要的时间算法步骤1. 确定二分查找范围int max_p 0; for(auto p : piles) { max_p max(max_p, p); } int left 0; // 不可行的下界 int right max_p 1; // 可行的上界开区间最小速度1每小时至少吃1根最大速度最大香蕉堆的大小一次吃完一堆使用开区间(left, right)left永远不可行right永远可行2. 二分查找主循环while(left 1 right) { int mid left (right - left) / 2; // 尝试的速度 // 计算以速度mid需要的时间 // 判断并更新边界 }3. 计算所需时间int tmp_hour 0; for(auto p : piles) { tmp_hour (p mid - 1) / mid; // 向上取整 if(tmp_hour h) break; // 提前退出优化 }对每堆香蕉p计算需要的小时数ceil(p / mid)使用整数向上取整技巧(p mid - 1) / mid累加总时间提前退出如果已超过h小时立即停止计算4. 判断并更新边界if(tmp_hour h) { left mid; // 速度太慢不可行 } else { right mid; // 速度可行尝试更小的 }5. 返回结果return right; // 最小的可行速度关键点二分查找对象吃香蕉的速度k不是数组索引验证条件以速度k吃完所有香蕉的时间≤ h搜索方向寻找满足条件的最小k边界处理使用开区间确保正确性时间复杂度寻找最大值O(n)二分查找O(log M)M为最大香蕉堆大小每次验证O(n)总时间O(n log M)示例piles [3,6,7,11] h 8 查找过程 1. 范围: k ∈ [1, 11] 2. 尝试 k6: 需要6小时 ≤ 8 → 可行 3. 尝试 k3: 需要10小时 8 → 不可行 4. 尝试 k4: 需要8小时 ≤ 8 → 可行 5. 尝试 k5: 需要8小时 ≤ 8 → 可行 6. 最终结果: k4函数源码class Solution { public: int minEatingSpeed(vectorint piles, int h) { int max_p0; for(auto p:piles){ max_pmax(max_p,p); } int left0; int rightmax_p1; while(left1right){ int mid(rightleft)/2; int tmp_hour0; for(auto p:piles){ tmp_hour(pmid-1)/mid; if(tmp_hourh) break; } if(tmp_hourh) leftmid; else rightmid; } return right; } };