Có ý tưởng giống bài Rate 2000, 1574D The Strongest Buil, div 2

Bài này đâu có phức tạp thế.

Ý tưởng là thế này:

Ta sắp xếp dãy theo thứ tự không giảm, khi đó sẽ luôn đứng sau trong dãy tổng đã sắp xếp. Do đó, khi chọ phần tử của dãy tổng, nếu chưa được chọn thì chắc chắn chưa đến lượt .

Do đó, ta có thuật toán: Dùng một hàng đợi ưu tiên (min):

• Ban đầu đẩy vào phần tử
• Lặp lại cho đến khi lấy đủ phần tử: lấy phần tử nhỏ nhất từ hàng đợi, giả sử phần tử lấy ra là thì sẽ đẩy vào hàng đợi , tất nhiên với điều kiện .