Tóm tắt đề bài: Cho ~N~ món đồ, mỗi món có khối lượng ~m_i~ và giá trị ~v_i~. Có ~K~ cái túi, mỗi cái túi chứa được tối đa một đồ vật với khối lượng tối đa ~c_i~. Tìm tổng giá trị lớn nhất có thể chọn để bỏ vào túi. Giới hạn: ~N,K \le 3.10^5~.

Nhận xét với dữ kiện “nhiều nhất một món cho một túi”, ta có thể giải quyết bài toán bằng thuật toán tham lam với các tư tưởng như sau:

• Đầu tiên ta quan tâm đến những món đồ có giá trị từ cao đến thấp, xem với mỗi món đồ, có tồn tại cái túi nào có thể chứa được hay không.

• Để tối ưu, với mỗi món đồ ta phải tìm cái túi có khối lượng nhỏ nhất chứa được.

Với tư tưởng trên, ta đơn giản tiến hành sắp xếp các món đồ theo giá trị tăng (hoặc giảm) của đại lượng ~v_i~. Ta tiến hành duyệt qua với mỗi món đồ, tiếp tục duyệt qua danh sách các cái túi, tìm cái túi có giá trị ~c_j~ nhỏ nhất với điều kiện chứa được đồ vật đó ~(c_j \geq m_i)~. Tuy nhiên, độ phức tạp lúc này sẽ là ~\mathcal{O}(N.K)~, dẫn đến TLE.

Vì vây, ta cần tối ưu hóa việc tìm kiếm cái túi phù hợp. Một cách đơn giản nhất ta có thể sử dụng thuật toán tìm kiếm nhị phân: tiến hành sắp xếp ~K~ cái túi theo khối lượng, sử dụng tìm kiếm nhị phân để tìm được cái túi nhỏ nhất với ~c_j \geq m_i~. Tuy nhiên, nếu sử dụng mảng, ta sẽ gặp khó trong việc xóa hoặc đánh dấu những cái túi đã được chọn (“nhiều nhất một món cho một túi”).

Các bạn có thể lưu danh sách cái túi với cấu trúc Set để thuận tiện trong việc sắp xếp cũng như xóa các phần tử.

Một lưu ý nhỏ trong việc cài đặt: vì CTDL Set lưu các giá trị khác nhau, vì vậy ta có thể gán nhãn cho các cái túi để biến chúng thành các “bộ giá trị khác nhau ”, cụ thể với mỗi cái túi sẽ có giá trị ~m_i~ và nhãn là ~i~.

Độ phức tạp thuật toán: ~\mathcal{O}((N \log{} N) + N \log{} K)~.

Các bạn có thể tham khảo cài đặt của mình ở mục hướng dẫn giải