leetcode 875. 爱吃香蕉的珂珂
2024-10-22 03:00:12
珂珂喜欢吃香蕉。这里有 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 <= 104
piles.length <= h <= 109
1 <= piles[i] <= 109
思路:使用二分法,取值从1-N,防止溢出,mid = (low+high)/2可以转换为int mid = (high - low) / 2 + low; 对pile/speed向上取整可以转换为(pile + speed - 1) / speed;注意total+的范围为long.
二分实现更新:
class Solution {
public:
long GetMax(vector<int> &piles, int k)
{
long time = 0;
for (auto i : piles) {
time += (i + k - 1) / k;
}
return time;
}
int GetMaxId(vector<int> &piles, int h)
{
int low = 1;
int high = 0;
for (auto i : piles) {
high = max(i, high);
}
int res = high;
while (low <= high) {
int mid = (high - low) / 2 + low;
long timeCnt = GetMax(piles, mid);
if (timeCnt > h) {
low = mid + 1;
} else {
high = mid - 1;
res = mid;
}
}
return res;
}
int minEatingSpeed(vector<int> &piles, int h)
{
return GetMaxId(piles, h);
}
};
代码:
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
long GetMax(vector<int> &piles, int k)
{
long time = 0;
for (auto i : piles) {
time += ceil(i / (k * 1.0)); // (pile + speed - 1) / speed;
}
return time;
}
int GetMaxId(vector<int> &piles, int h)
{
int low = 1;
int high = 0;
for (auto i : piles) {
high = max(i, high);
}
int res = high;
while (low < high) {
int mid = (high + low) / 2; //int speed = (high - low) / 2 + low;
long timeCnt = GetMax(piles, mid);
if (timeCnt > h) {
low = mid + 1;
} else {
high = mid;
res = mid;
}
}
return res;
}
int minEatingSpeed(vector<int> &piles, int h)
{
return GetMaxId(piles, h);
}
int main()
{
vector<int> piles = { 312884470 };
int h = 968709470;
int res = minEatingSpeed(piles, h);
cout << "result: " << res << endl;
return 0;
}
最新文章
- 40GbE网络之后
- Oracle 11g RAC 环境打PSU补丁的详细步骤
- UI控件(UIAlertController)
- AMD and CMD are dead之KMDjs集成Blob一键下载全部build包
- centos6安装python3.4和pip3
- mysql 修改root密码
- 【POJ】【2891】Strange Way to Express Integers
- Data Flow ->;>; Term Extraction
- Fast特征检测
- jquery 中ajax的参数
- 牛掰啊,github+svn+FB进行项目开发
- Mesos源码分析(1): Mesos的启动过程总论
- Selenium断言的使用,等待
- java中如何模拟真正的同时并发请求?
- python绝对路径和相对路径
- 《Effective Java 第三版》新条目介绍
- [CQOI2014]排序机械臂
- 经典]Linux内核中ioremap映射的透彻理解【转】
- Linux说明书 - man浅谈
- PHP filter_input() 函数