ข้อ 56 · LC875 Koko Eating Bananas (โกโกะกินกล้วย) 🟡

โจทย์ (LC875): โกโกะมีกล้วย n กอง โดยกองที่ i มี piles[i] ลูก ยามจะกลับมาใน h ชั่วโมง โกโกะเลือกความเร็วในการกิน k (กล้วยต่อชั่วโมง) แต่ละชั่วโมงเลือกกินจากกองใดกองหนึ่งได้สูงสุด k ลูก ถ้ากองนั้นมีน้อยกว่า k ลูก โกโกะจะกินหมดกองแล้วไม่กินกองอื่นต่อในชั่วโมงนั้น ให้หาความเร็ว k ที่น้อยที่สุดที่ทำให้กินกล้วยหมดทุกกองได้ภายใน h ชั่วโมง

แนวทาง — ต้องใช้อะไร & คิดยังไง

โครงสร้างที่ใช้: binary search on answer (ค้นบนช่วงคำตอบ) เราไม่ได้ search (ค้นหา) ใน array แต่ค้นบน answer space (ช่วงคำตอบ) คือ speed k ที่เป็นไปได้ speed k ยิ่งมากยิ่งกินทันแน่ ๆ (monotonic เท็จ-จริง แบบขั้นบันได) จึง binary search หา speed น้อยสุดที่ทัน

คิดแบบง่าย/ช้าก่อน: วิธี naive คือ iterate (วน) ลอง k = 1, 2, 3, ... จนกว่าจะทัน เป็น O(max(piles) * n) เพราะความสัมพันธ์เป็นขั้นบันได (ถ้า k ทันแล้ว k ที่มากกว่าก็ทัน) เราจึง binary search หา boundary (จุดพลิก) จากไม่ทันเป็นทัน เหลือ O(n log(max))

1. เขียน function (ฟังก์ชัน) hours_needed(k) = ผลรวมของ ceil(pile / k) ทุกกอง (ปัดขึ้นเพราะกินข้ามกองไม่ได้)
2. ตั้ง answer space lo = 1, hi = max(piles) (เร็วสุดที่จำเป็น)
3. ระหว่าง lo < hi: compute mid ถ้า hours_needed(mid) <= h แสดงว่า feasible (ทัน) ลองช้าลงอีก ตั้ง hi = mid
4. ไม่งั้น mid ช้าไป กินไม่ทัน ตั้ง lo = mid + 1; จบ loop return lo คือ speed น้อยสุดที่ทัน

ไล่ทีละสเต็ป

จำลอง piles = [3,6,7,11], h = 8 ช่วง lo = 1, hi = 11:

import math

def min_eating_speed(piles, h):
    def hours_needed(k):
        # ที่ความเร็ว k แต่ละกองใช้เวลา ceil(pile / k) ชั่วโมง
        return sum(math.ceil(pile / k) for pile in piles)

    lo, hi = 1, max(piles)     # ช่วงความเร็วที่เป็นไปได้
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(mid) <= h:
            hi = mid           # เร็ว mid ก็ทัน ลองช้าลงอีก (เก็บ mid ไว้)
        else:
            lo = mid + 1       # mid ช้าไป กินไม่ทัน ต้องเร็วขึ้น
    return lo                  # ความเร็วน้อยสุดที่ยังทัน

print(min_eating_speed([3, 6, 7, 11], 8))        # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5))  # 30

4
30