Mua Quà

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

1. 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$.
2. Để 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).
3. Vì $N\le 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

1. Tính tổng chi phí $c_i=P_i+S_i$ cho mỗi món.
2. Sắp xếp các món theo $c_i$ tăng dần.
3. 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.
4. 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)$