Koko Eating Bananas trong C++

N đống chuối, đống i có piles[i] quả. Vệ sĩ quay lại sau H giờ. Koko ăn K quả/giờ (chọn một đống, ăn K hoặc hết đống). Tìm K nhỏ nhất để ăn hết trong H giờ.

Ví dụ: [3,6,7,11], H=8 → 4.

Giải pháp Binary Search:

• ok(x): tính giờ cần với tốc độ x, trả về true nếu ≤ H

• low=1, high=max(piles)

• While low

• Trả về high

Ví dụ

#include <bits/stdc++.h> using namespace std; typedef long long lli; class Solution {    public:    bool ok(vector<int>& a, int x, int H){ int time=0; for(int v:a){ time += v/x + (v%x?1:0); } return time <= H; }    int minEatingSpeed(vector<int>& piles, int H) {       int low=1, high=0; for(int v:piles) high=max(high,v);       while(low < high){ int mid = low + (high-low)/2; if(ok(piles,mid,H)) high=mid; else low=mid+1; } return high; } }; int 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