Koko Eating Bananas

Q: Độ phức tạp thời gian của bài toán Koko Eating Bananas là bao nhiêu?

Tìm kiếm nhị phân chạy trong thời gian O(n log m) , trong đó n là số đống và m là đống lớn nhất: khoảng log2(m) lần kiểm tra, 30 lần khi m = 10^9 , mỗi lần đọc từng đống một lần. Bộ nhớ phụ cần dùng là O(1) .

Q: Giới hạn dưới và giới hạn trên của tốc độ là bao nhiêu?

Cận trên là đống lớn nhất: với tốc độ đó, mỗi đống chỉ mất một giờ, nên luôn vừa đủ thời gian. Cận dưới là 1, và bạn có thể tăng cận dưới lên bằng tổng số quả chuối chia cho h , rồi làm tròn lên, vì Koko ăn nhiều nhất k quả chuối mỗi giờ.

Q: Làm thế nào để chia và làm tròn lên với số nguyên?

Dùng (p + k-1) / k với phép chia số nguyên. Cộng thêm k-1 sẽ đẩy phần dư vượt qua bội số tiếp theo của k , còn bội số chính xác thì giữ nguyên: với tốc độ 4, 10 cho kết quả 13 / 4 = 3 , còn 8 cho kết quả 11 / 4 = 2 . Không cần dùng số thực.

Trung bìnhTìm kiếm nhị phân

+10

Koko có n đống chuối, trong đó đống i có piles[i] quả chuối, và có h giờ. Cô chọn một tốc độ ăn k, tức là một số nguyên chỉ số quả chuối ăn mỗi giờ, rồi giữ nguyên tốc độ đó. Mỗi giờ, cô ăn k quả chuối từ một đống; nếu đống đó còn ít hơn k quả, cô ăn hết rồi nghỉ cho đến hết giờ. Hãy trả về k nhỏ nhất giúp cô ăn hết tất cả các đống trong vòng h giờ.

Hàm

minEatingSpeed(piles: integer-array, h: integer) → integer

pilesinteger-array: số quả chuối trong mỗi đống
hinteger: số giờ Koko có
Trả vềinteger: tốc độ ăn nguyên nhỏ nhất, tính bằng số quả chuối mỗi giờ, để ăn hết mọi đống chuối trong vòng h giờ

Ràng buộc

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, vì vậy luôn tồn tại đáp án.

Ví dụ

Đầu vào: piles = [4, 10, 7, 3]h = 6
Đầu ra: 5
Giải thích: Ở tốc độ 5, các đống 4, 10, 7 và 3 cần lần lượt 1, 2, 2 và 1 giờ: tổng cộng là 6 giờ, vừa khớp. Ở tốc độ 4, chúng cần lần lượt 1, 3, 2 và 1 giờ, tổng cộng là 7 giờ.

Câu hỏi mở rộng

Bài toán tương tự: Koko ăn hết từng đống theo thứ tự, tối đa k quả chuối mỗi ngày, trong vòng d ngày. k nhỏ nhất là bao nhiêu, và bạn cần thay đổi điều gì trong cách tìm kiếm?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Đáp án là một tốc độ, không phải vị trí trong mảng, và điều đó khiến ta khó nhận ra cách tìm kiếm nhị phân (binary search). Kiểm tra một tốc độ cần duyệt qua các đống một lượt, và nếu tốc độ k hoàn thành đúng hạn thì mọi tốc độ cao hơn cũng vậy. Vì thế, hãy tìm kiếm nhị phân trong khoảng tốc độ từ 1 đến đống lớn nhất: khoảng 30 lần kiểm tra thay vì lên đến một tỷ.

Thử mọi tốc độ, bắt đầu từ 1 trở lên

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Koko không bao giờ chuyển sang đống khác trong một giờ, vì vậy một đống có p quả chuối sẽ mất p / k giờ sau khi làm tròn lên: với tốc độ 4, ăn 10 quả sẽ mất 3 giờ. Hãy thử các tốc độ 1, 2, 3, cứ thế tiếp tục, rồi trả về tốc độ đầu tiên có tổng thời gian không vượt quá h. Đây là tốc độ nhỏ nhất vì mọi tốc độ thấp hơn đều không đáp ứng được, và vòng lặp dừng ở tốc độ bằng số chuối trong đống lớn nhất, khi đó mỗi đống chỉ mất một giờ.

Với m là số chuối trong đống lớn nhất, ta cần tối đa m lần kiểm tra cho n đống: khoảng 5 × 10^12 bước với 5000 đống có gần 10^9 quả chuối mỗi đống và h = 5000.

Thuật toán

Đặt speed = 1.
Đếm số giờ ở tốc độ này: với mỗi đống, cộng (pile + speed-1) / speed, dùng tổng 64-bit.
Nếu tổng không lớn hơn h, trả về speed.
Nếu không, tăng speed thêm 1 rồi đếm lại.

def minEatingSpeed(piles, h):
    speed = 1
    while True:
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # a started pile costs a whole hour
        if hours <= h:
            return speed
        speed += 1

Tìm kiếm nhị phân theo tốc độ

Ý tưởng

Khi tốc độ tăng, mỗi đống cần số giờ bằng hoặc ít hơn, vì vậy câu trả lời cho câu hỏi “tốc độ này có hoàn thành kịp giờ không?” sẽ là không, không, không, rồi đến có từ đáp án trở đi. Tìm kiếm nhị phân tìm ra đáp án có đầu tiên.

Giữ một phạm vi từ lo đến hi luôn chứa đáp án, bắt đầu từ 1 đến đống lớn nhất, vì tốc độ đó cần một giờ cho mỗi đống nên vẫn kịp. Nếu tốc độ ở giữa mid vẫn kịp, đáp án là mid hoặc chậm hơn, nên đặt hi = mid. Nếu không, mọi tốc độ chậm hơn cũng đều không kịp, nên đặt lo = mid + 1. Khi lo bằng hi, đó là đáp án.

Trong ví dụ đầu tiên, phạm vi bắt đầu từ 1 đến 10. Tốc độ 5 vẫn kịp, nên phạm vi trở thành 1 đến 5; tốc độ 3 cần 10 giờ, nên phạm vi còn 4 đến 5; tốc độ 4 cần 7 giờ, nên phạm vi còn 5 đến 5.

Thuật toán

Đặt lo = 1 và đặt hi bằng đống lớn nhất.
Khi lo < hi, lấy mid = lo + (hi - lo) / 2.
Đếm số giờ với tốc độ mid: cộng (pile + mid-1) / mid cho mỗi đống, vào một tổng 64 bit.
Nếu tổng không vượt quá h, đặt hi = mid; nếu không, đặt lo = mid + 1.
Trả về lo.

def minEatingSpeed(piles, h):
    lo, hi = 1, max(piles)  # the largest pile always works: one hour per pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        hours = 0
        for pile in piles:
            hours += (pile + mid - 1) // mid
        if hours <= h:
            hi = mid  # mid works, so the answer is mid or slower
        else:
            lo = mid + 1  # mid is too slow, so the answer is faster
    return lo

Lỗi thường gặp và trường hợp biên

Tràn số giờ. Với tốc độ 1, 5000 đống chuối, mỗi đống 10^9 quả, cần 5 × 10^12 giờ, vượt giới hạn 32 bit, khiến tổng bị tràn có thể làm tốc độ chậm vượt qua. Hãy đếm bằng 64 bit hoặc dừng ngay khi tổng vượt quá h.
Làm tròn xuống. 10 / 4 cho kết quả 2, nhưng đống chuối đó cần 3 giờ.
Bắt đầu phạm vi từ 0. Khi đó mid có thể bằng 0 và phép tính số lượng sẽ chia cho 0.
Đặt hi = mid - 1 khi mid phù hợp. Cách này có thể loại bỏ đáp án.
Bắt đầu với hi nhỏ hơn đống chuối lớn nhất. Khi h bằng số đống chuối, mọi tốc độ thấp hơn đều không đáp ứng yêu cầu, và thuật toán tìm kiếm sẽ trả về một trong các tốc độ đó.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán Koko Eating Bananas là bao nhiêu?

Tìm kiếm nhị phân chạy trong thời gian O(n log m), trong đó n là số đống và m là đống lớn nhất: khoảng log2(m) lần kiểm tra, 30 lần khi m = 10^9, mỗi lần đọc từng đống một lần. Bộ nhớ phụ cần dùng là O(1).

Giới hạn dưới và giới hạn trên của tốc độ là bao nhiêu?

Cận trên là đống lớn nhất: với tốc độ đó, mỗi đống chỉ mất một giờ, nên luôn vừa đủ thời gian. Cận dưới là 1, và bạn có thể tăng cận dưới lên bằng tổng số quả chuối chia cho h, rồi làm tròn lên, vì Koko ăn nhiều nhất k quả chuối mỗi giờ.

Làm thế nào để chia và làm tròn lên với số nguyên?

Dùng (p + k-1) / k với phép chia số nguyên. Cộng thêm k-1 sẽ đẩy phần dư vượt qua bội số tiếp theo của k, còn bội số chính xác thì giữ nguyên: với tốc độ 4, 10 cho kết quả 13 / 4 = 3, còn 8 cho kết quả 11 / 4 = 2. Không cần dùng số thực.

def minEatingSpeed(piles, h):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

piles = [4, 10, 7, 3]
h = 6

Đầu ra mong đợi