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, 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
Ý 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)
Ý 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