Hướng dẫn giải của Phiếu Giảm Giá Bò
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.
Tác giả:
Lời giải: Phiếu Giảm Giá Bò
Hướng tiếp cận
Sắp xếp các con bò theo giá phiếu, sử dụng priority queue.
Thuật toán
Binary search trên đáp án (số bò mua). Với mỗi , chọn bò giá rẻ nhất (có thể dùng phiếu cho tối đa con). Greedy: sắp xếp theo giá coupon, dùng heap để swap phiếu khi có lợi hơn.
Độ phức tạp
- Thời gian:
Bình luận