Tính số nhóm có thể chia được:

Tính tổng dồn của các ai, chặt nhị phân (0..tổng) tìm số nhóm có thể chia được;

Xét số nhóm là x, duyệt dãy số từ 1..n:

• Nếu ~ai < x~ -> ~S=S + ai~
• Nếu ~ai ≥ x~ -> ~S=S + x~

Số nhóm ~x~ là khả thi khi ~S ≥ K*x~

Áp dụng:

Ban đầu chia tất cả n đoàn, xem được bao nhiêu nhóm; Sắp xếp n đoàn theo số người tăng dần để giảm độ phức tạp; Xây dựng cây IT, mỗi nút quản lý hai thuộc tính:

• Tổng số người;
• Số đoàn tham gia;

Các nút lá chứa hai thuộc tính ~(ai, 1)~, lưu ý ai được sắp tăng dần. Cập nhật nút cha như sau: cộng tổng lần lượt của hai thuộc tính;

Sau đó, bỏ đi đoàn thứ ~n~, cập nhật lại cây IT, xem thử chia được bao nhiêu nhóm; Sau đó, bỏ đi đoàn thứ ~n-1~, cập nhật lại cây IT, xem thử chia được bao nhiêu nhóm Tiếp tục, cho đến khi bỏ đi đoàn thứ ~n – R + 1~, tính số nhóm chia được.

Code mẫu : https://www.ideone.com/CfTJpn