資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告