DISCOUNT2 - Mua 4 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:
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
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 mặt hàng thì siêu thị sẽ giảm giá cho mặt hàng có giá cao nhất trong 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 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ị.(~ 1 \le N \le 10^5 ~)
- Dòng thứ hai ghi N số nguyên dương ~ c_i ~. Hai số liên tiếp được ghi cách nhau một khoảng trắng.(~ 1 \le c_i \le 10^9 ~)
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
Ta mua mặt hàng 1,2,3,4 sẽ được khuyến mại mặt hàng 1 nên cần trả 15 đồng, mua mặt hàng thứ 5 cần trả 8 đồ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
Mình viết lại đề cho dễ hiểu, đọc cái đề trên chả hiểu gì. Có một danh sách các mặt hàng trong siêu thị có giá tiền là ci, mỗi mặt hàng chỉ có 1. Bạn chọn lấy 4 thứ để mua, siêu thị sẽ tặng bạn cái có giá cao nhất (bạn không phải trả tiền cho cái đó) và bạn chỉ phải trả tiền cho 3 thứ còn lại. Tính số tiền ít nhất để mua hết hàng trong siêu thị. Ví dụ: có 5 món có giá lần lượt là: 10 3 7 5 8. Bạn chọn mua 4 thứ có giá lần lượt là: 3 7 5 8, siêu thị tặng cái có giá cao nhất ở đây là 8, bạn sẽ phải bỏ tiền mua: 3 + 7 + 5 = 15 đồng cho 4 thứ trên và 10 đồng cho cái còn lại tổng là 25 đồng (không phải số tiền nhỏ nhất). Bạn chọn mua 4 thứ: 10 3 7 5 thì siêu thị tặng bạn cái có giá cao nhất là 10 đồng bạn chỉ phải bỏ tiền mua 3 thứ còn lại: 3 + 7 + 5 = 15 đồng. Rồi mua nốt cái còn lại trong siêu thị với giá 8 đồng tổng là 23 đồng (đây là số tiền ít nhất để mua hết hàng)
Đề ghi khó hiểu quá: "cứ mua mặt hàng" mua bao nhiêu mặt hàng phải ghi rõ là "cứ mua 4 mặt hàng" thì siêu thị "sẽ giảm giá" giảm bao nhiêu tiền? ghi là tặng luôn cái đấy đi. cho mặt hàng có giá cao nhất trong 4 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 mặt hàng của siêu thị. Chỗ này lại thích dùng từ Hán Việt là "tối thiểu" nói là ít nhất hay nhỏ nhất đỡ đau đầu.
include<string>
include<iostream>
include<algorithm>
include<vector>
include<map>
include<set>
include<iomanip>
include <climits>
include <cmath>
using namespace std;
bool cmp(pair<int,int> a,pair<int,int> b) { if(a.second!=b.second) { return b.second>a.second; } else { return a.first<b.first; } }
int main() { int n;cin>>n; int a[n]; for(int i=0;i<n;++i) {cin>>a[i];}; int tong=0; sort(a,a+n); for(int i=0;i<n;++i) { tong=tong+a[i]; } int b=n/4; int khuyenmai=0; for(int i=1;i<=b;++i) {
}
Ý tưởng: Mua 3 mặt hàng có giá tiền nhỏ nhất + 1 mặt hàng có giá tiền cao nhất => được giảm giá nhiều nhất. Tính tổng số tiền rồi - phần được giảm giá sẽ ra kết quả.
CƯỜNG GIẢ HỌ ĐINH. VẠN CỔ TỐI CƯỜNG
sao test 2 fix mãi không đúng nhỉ