DISCOUNT - Mua 3 tặng 1
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
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, PyPy, Python, Ruby, Rust, Scratch, Swift
Siêu thị Vincom Sơn La đang có đợt giảm giá. Siêu thị có ~n~ mặt hàng đánh số từ ~1~ đến ~n~, mặt hàng thứ ~i~ có giá là ~c_i~. Trong đợt giảm giá này, cứ mua ~3~ mặt hàng thì siêu thị sẽ giảm giá cho mặt hàng có giá cao nhất trong ~3~ mặt hàng đó.
Yêu cầu: Hãy tính số tiền tối thiểu cần bỏ ra để mua hết ~n~ mặt hàng của siêu thị.
Input
- Dòng đầu tiên ghi số ~n~ là số mặt hàng của siêu thị;
- Dòng thứ hai ghi ~n~ số nguyên dương ~c_1,c_2,…,c_n\ (1≤c_i≤10^9)~. Hai số liên tiếp được ghi cách nhau một khoảng trắng.
Giới hạn:
- Subtask #1: 60% số điểm của bài có ~1≤n≤1000~;
- Subtask #2: 40% số điểm còn lại của bài có ~1000< n≤10^5~.
Output
- Một số nguyên duy nhất là số tiền tối thiểu cần bỏ ra để mua hết ~n~ mặt hàng của siêu thị.
Sample
Input #1
5
10 3 7 5 8
Output #1
23
Hint
Giải thích: Ta mua mặt hàng ~1,2,3~ sẽ được khuyến mại mặt hàng ~1~ nên cần trả ~10~ đồng, mua mặt hàng ~4,5~ cần trả ~13~ đồng nữa. Tổng cộng cần trả ~23~ đồng.
Problem source: Chuyên Sơn La Online Judge
Bình luận
sontung accoc
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Ý tưởng: tính tổng tất cả món đồ rồi trừ n/3 món đồ đầu tiên (nhớ sort ngược lại)
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Ý tưởng: ta có thể mua 3 món đồ không cần nằm cạnh nhau cũng được (trong đó có 2 món có giá tiền thấp nhất và 1 món có giá tiền lớn nhất).
CƯỜNG GIẢ HỌ ĐINH. VẠN CỔ TỐI CƯỜNG