Giả sử chúng ta có N đống chuối, đống thứ i có đống [i] chuối. Tại đây lính canh đã đi và sẽ quay lại sau giờ H. Koko có thể quyết định tốc độ ăn chuối mỗi giờ của mình là K. Mỗi giờ, cô ấy lấy một đống chuối và ăn K quả chuối từ đống đó. Nếu đống chuối có ít hơn K thì thay vào đó cô ấy sẽ ăn hết và không ăn chuối nữa trong giờ này. Hãy xem Koko thích ăn chậm, nhưng vẫn muốn ăn hết chuối trước khi lính canh quay lại. Chúng ta phải tìm số nguyên K nhỏ nhất sao cho cô ấy có thể ăn hết số chuối trong vòng H giờ.
Vì vậy, nếu đầu vào là [3,6,7,11] và H =8, thì đầu ra sẽ là 4.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một phương thức có tên ok (), phương thức này sẽ nhận mảng a, hai giá trị x và h
-
thời gian:=0
-
cho tôi trong phạm vi từ 0 đến kích thước của một
-
time:=time + a [i] / x
-
time:=time + i khi [i] mod x bằng 0
-
-
trả về true khi thời gian <=H
-
Từ phương thức chính, hãy làm như sau
-
n:=kích thước của mảng cọc, đặt tổng:=0, thấp:=1, cao:=0
-
cho tôi trong phạm vi từ 0 đến n - 1
-
cao:=tối đa cọc [i] và cao
-
-
trong khi thấp
-
giữa:=low + (cao - thấp) / 2
-
nếu ok (cọc, giữa, H) là đúng, thì đặt cao:=giữa, ngược lại thấp:=giữa + 1
-
nếu ok (cọc, giữa, H) là đúng, thì đặt cao:=giữa, ngược lại thấp:=giữa + 1
-
-
trả về cao
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[3,6,7,11] 8
Đầu ra
4