Hướng dẫn giải của HSG THPT Thanh Hóa 2021 - Mua Quà
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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))~
Bình luận
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.