Hướng giải: Vũ điệu của đàn bò

Tiến hành tìm kiếm nhị phân cho đáp án của bài toán. Với mỗi giá trị ~k~, cần kiểm tra xem tổng thời gian biểu diễn có vượt quá ~t_{max}~ hay không.

Trong số các con bò đang biểu diễn trên sân khấu, ta cần tìm ra con bò có thời gian biểu diễn ngắn nhất để tiến hành thay thế con bò tiếp theo vào. Có thể sử dụng cấu trúc Hàng đợi ưu tiên (Priority Queue) để xử lý nhanh thao tác tìm và thêm con bò phù hợp.

Ban đầu, thêm các con bò có chỉ số ~1,2,...,k~ vào Hàng đợi ưu tiên và tổng thời gian biểu diễn ~t=0~. Duyệt qua với mỗi chỉ số ~k+1,...,n~:

• Để thêm con bò thứ ~i~ vào hàng đợi, trước tiên cần tìm và loại bỏ một con bò có thời gian biểu diễn ngắn nhất khỏi hàng đợi tương ứng, đồng thời cập nhật ~t=top~ với ~top~ là phần tử được loại bỏ khỏi hàng đợi. Sau đó, thêm con bò thứ ~i~ với giá trị ~d_i+t~ vào hàng đợi.

Lưu ý sau khi hoàn thành thêm toàn bộ ~n~ con bò vào hàng đợi, cần xử lý loại bỏ các con bò cho đến khi hàng đợi rỗng và cập nhật tổng thời gian biểu diễn ~t~.

Độ phức tạp: ~O(n.log^2(n))~.