Editorial for HSG THPT Thanh Hóa 2021 - Mua Quà
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Nhận xét :
Với một đơn hàng thì số tiền cần trả là giá của món quà đắt nhất của đơn hàng đó. Nên ta cần tìm cách để chọn những món quà càng đắt mà không cần phải trả tiền.
Từ đó ta có thuật toán tham lam : Với một dãy ~a_1 \le a_2... \le a_n~.
Ta sẽ xây dựng một đơn hàng có giá là ~a_n~ với nhiều món quà được chọn nhất có thể. Khi xây dựng xong, ta xóa dãy con của đơn hàng đó đi, và tiếp tục thực hiện cho đến khi không còn món quà nào.
Subtask 1
Ta sắp xếp lại giá của các món quà tăng dần. Thực hiện các thao tác như trên nhận xét.
Độ phức tạp : ~O(n ^ 2)~
Subtask 2
Ta có thể dùng ~\textbf{multiset}~ để thực hiện thao tác xây dựng đơn hàng và xóa các phần tử trong đơn hàng đó đi.
Độ phức tạp : ~O(n \times log(n))~
Comments
Phải sắp xếp từ đắt nhất đến rẻ nhất để tối ưu hóa vì món quà đắt nhất chắc chắn sẽ quyết định giá của một đơn hàng nào đó (vì không có món nào đắt hơn để "che" nó đi). Vì ta đằng nào cũng phải trả tiền cho món đắt nhất này, ta nên tận dụng nó để ghép "miễn phí" nhiều món quà khác nhất có thể.ví dụ 5 10 {10, 11, 12, 25, 27} ta sẽ có 3 đơn là (27,12); (25,11) và (10) => tổng là 27+25+10=62 nếu sắp xếp tăng dần ta có (10,25);(11,27) và (12) tổng là 25+27+12=64.