BOOKSHOP - Tiệm sách
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.1s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Nhà sách thành phố đang có chương trình ưu đãi "mua 3 lấy tiền 2 quyển đắt hơn". Tất nhiên khách hàng cũng có thể mua ít hơn hoặc nhiều hơn 3 quyển và tùy thuộc vào cách mua 3 cuốn sách 1 lượt, cuốn rẻ nhất sẽ được miễn phí.
Giả sử anh Hiểu muốn mua 7 quyển sách có giá là: 2, 3, 4, 4, 6, 9, 10. Nếu:
- Lượt 1 anh mua 3 quyển có giá 10, 3, 2 thì quyển có giá 2 sẽ được miễn phí.
- Lượt 2 anh mua 3 quyển có giá 6, 4, 4 thì quyển có giá 4 sẽ được miễn phí.
- Lượt 3 anh mua 1 quyển có giá 9 thì hiển nhiên sẽ không được miễn phí quyển nào vì chỉ mua 1 quyển sách.
Yêu cầu: Tính số tiền nhỏ nhất phải trả cho ~n~ quyển sách
Input
Dòng đầu là số tự nhiên ~n~ (~n~ ~\le~ ~10^5~)
Dòng thứ hai gồm ~n~ số tự nhiên ~a_i~ là giá của cuốn sách thứ ~i~ (~1~ ~\le~ ~a_i~ ~\le~ ~10^6~)
Output
Gồm 1 số duy nhất là số tiền ít nhất phải trả cho ~n~ cuốn sách
Sample
Input #1
6
6
4
5
5
5
5
Output #1
21
Bình luận
Ý tưởng: Cứ chọn 3 cuốn sách đắt nhất mua trước, ta sẽ đc miễn phí cuốn rẻ nhất trong 3 cuốn đó. Cứ như vậy đến khi mua hết n cuốn sách.