Koko Eating Bananas ใน C++

คำอธิบายปัญหา

มี N กองกล้วย piles[i] ลูก Koko กินได้ K ลูก/ชั่วโมง เลือกกองกินจนหมดกองนั้นก่อนจึงเปลี่ยนกอง ถ้ากองน้อยกว่า K กินหมดในชั่วโมงนั้น ประตูจะเปิดใน H ชั่วโมง ต้องการ K ต่ำสุดที่กินหมดทัน

ตัวอย่าง: [3,6,7,11], H=8 → K=4

วิธีแก้ปัญหา (Binary Search)

1. K อยู่ในช่วง [1, max(piles)]
2. ตรวจสอบ K ไหนกินหมดได้ภายใน H ชั่วโมง: hours = Σ ceil(piles[i]/K)
3. Binary search หา K ต่ำสุดที่ hours <= H

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool canEat(vector<int>& piles, int K, int H) {
        long long hours = 0;
        for(int p : piles) {
            hours += (p + K - 1) / K; // ceil division
            if(hours > H) return false;
        }
        return hours <= H;
    }
    
    int minEatingSpeed(vector<int>& piles, int H) {
        int left = 1, right = *max_element(piles.begin(), piles.end());
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(canEat(piles, mid, H)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

int main() {
    vector<int> v = {3,6,7,11};
    Solution ob;
    cout << ob.minEatingSpeed(v, 8);
    return 0;
}

อินพุต

[3,6,7,11] 8

เอาต์พุต

4