Book Allocation Problem

Bắt đầu từ L = max(pages), vì một bạn phải mang cuốn sách dày nhất, rồi tăng L từng trang một cho đến khi số lượng tính theo cách tham lam phù hợp với students. Mọi giới hạn thấp hơn đều không phù hợp, vậy nên giới hạn đầu tiên phù hợp chính là đáp án. Trong ví dụ đầu tiên, mọi giới hạn từ 50 đến 64 đều cần bốn học sinh, còn 65 cần ba học sinh: 16 lần kiểm tra.

Đáp án có thể bằng tổng số sách trên kệ: một học sinh và 5000 cuốn sách, mỗi cuốn có 10^5 trang, tức là khoảng 5 × 10^8 giới hạn, mỗi giới hạn cần duyệt qua 5000 cuốn sách. Trong cột thời gian, A là đáp án và m là số trang của cuốn sách dày nhất.

Số lượng học sinh tham lam là số học sinh ít nhất cần có để chia sách theo giới hạn L. So sánh từng học sinh với cách chia bất kỳ khác, mỗi học sinh trong cách chia tham lam chỉ dừng lại khi cuốn sách tiếp theo không vừa, vì vậy họ luôn đi được ít nhất đến vị trí đó trên kệ. Có ít học sinh hơn số bạn có cũng không sao: một học sinh đang giữ hai cuốn có thể đưa một cuốn cho học sinh chưa có cuốn nào, và không ai phải mang thêm sách.

Vì vậy, L phù hợp chính xác khi số lượng học sinh tham lam không vượt quá students. Bất kỳ giới hạn L nào phù hợp thì L+1 cũng phù hợp, nên tìm kiếm nhị phân sẽ tìm ra giới hạn nhỏ nhất phù hợp.

Khoảng tìm kiếm bắt đầu từ giá trị lớn hơn giữa max(pages) và phần chia trung bình, tức total / students được làm tròn lên, vì tải trọng lớn nhất ít nhất cũng bằng cả hai giá trị đó. Giới hạn trên là total. Trong ví dụ đầu tiên, khoảng đó là từ 54 đến 160, và thuật toán thử 107, 80, 67, 60, 64, 66 rồi 65.