Hướng dẫn giải của 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.

Tác giả: huunguyen

Lời giải: Mua Quà

Hướng tiếp cận

Vì chỉ có một phiếu giảm giá, ta thử dùng phiếu cho từng món quà một. Với mỗi lựa chọn món được giảm giá, ta tham lam mua thêm các món còn lại rẻ nhất trong ngân sách còn lại.

Nhận xét quan trọng

Tổng chi phí một món là $P_{i} + S_{i}$ . Với món được giảm giá, chi phí là $P_{i} / 2 + S_{i}$ .
Để tối đa số món mua được, sau khi dùng phiếu cho một món, ta nên mua các món còn lại theo thứ tự tổng chi phí tăng dần (tham lam).
Vì $N \leq 1000$ , ta có thể thử dùng phiếu cho từng món và tính kết quả trong $O (N \log N)$ mỗi lần.

Thuật toán

Tính tổng chi phí $c_{i} = P_{i} + S_{i}$ cho mỗi món.
Sắp xếp các món theo $c_{i}$ tăng dần.
Với mỗi món j từ 0 đến N−1 (thử dùng phiếu cho món j):
- Chi phí của món $j$ khi dùng phiếu: $P_{j} / 2 + S_{j}$ .
- Duyệt các món theo thứ tự đã sắp xếp: bỏ qua món $j$ , mua lần lượt từ rẻ đến đắt cho đến khi hết ngân sách.
- Lưu số món mua được.
Lấy kết quả tốt nhất trong tất cả các thử nghiệm.

Độ phức tạp

Thời gian: $O (N^{2})$
Bộ nhớ: $O (N)$

Bình luận

Không có bình luận tại thời điểm này.