数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 实现香蕉吃光问题
假设我们有 N 堆香蕉，第 i 堆有 piles[i] 根香蕉。警卫已经离开，将在 H 小时后回来。Koko 可以决定她每小时吃香蕉的速度 K。每小时，她选择一堆香蕉，并吃掉 K 根。如果这堆香蕉少于 K 根，那么她会全部吃完，并且在这一小时内不会再吃任何香蕉。考虑 Koko 喜欢慢慢吃，但仍然希望在警卫回来之前吃完所有香蕉。我们必须找到最小的整数 K，使得她在 H 小时内吃完所有香蕉。
所以如果输入像 [3,6,7,11]，并且 H = 8，那么输出将是 4。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为 ok() 的方法，它将接收数组 a、两个值 x 和 h
time := 0
for i in range 0 到 a 的大小
time := time + a[i] / x
当 a[i] mod x 为 0 时，time := time + i
当 time <= H 时返回 true
从主方法执行以下操作
n := piles 数组的大小，设置 sum := 0，low := 1，high := 0
for i in range 0 到 n – 1
high := piles[i] 和 high 的最大值
while low < high
mid := low + (high – low ) /2
如果 ok(piles, mid, H) 为真，则设置 high := mid，否则 low := mid + 1
如果 ok(piles, mid, H) 为真，则设置 high := mid，否则 low := mid + 1
返回 high
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
bool ok(vector <int>& a, int x, int H){
int time = 0;
for(int i = 0; i < a.size(); i++){
time += a[i] / x;
time += (a[i] % x ? 1 : 0);
}
return time <= H;
}
int minEatingSpeed(vector<int>& piles, int H) {
int n = piles.size();
lli low = 1;
lli sum = 0;
lli high = 0;
for(int i = 0; i < n; i++)high = max((lli)piles[i], high);
while(low < high){
int mid = low + (high - low) / 2;
if(ok(piles, mid, H)){
high = mid;
}else{
low = mid + 1;
}
}
return high;
}
};
main(){
vector<int> v = {3,6,7,11};
Solution ob;
cout << (ob.minEatingSpeed(v, 8));
}输入
[3,6,7,11] 8
输出
4
更新于: 2020-04-30
350 次浏览
广告