[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Bài 4. Mua sách (5 điểm)
Một lời quảng cáo chào hàng trong một hiệu sách “mua 3, tặng 1, trả tiền 2”. Khách hàng được thông báo là khi mua ba quyển sẽ được tặng một quyển có giá rẻ nhất trong ba quyển đó. Tất nhiên, khách hàng có thể mua nhiều sách và phụ thuộc vào việc sắp xếp các quyển sách vào mỗi nhóm ba quyển để được miễn phí quyển có giá rẻ nhất trong nhóm đó.
Ví dụ: Khách hàng lấy 7 quyển sách có giá trị lần lượt là 10, 3, 2, 4, 6, 4, 9. Nếu các quyển sách này được sắp thành nhóm: (10, 3, 2), (4, 6, 4) và (9) thì khách hàng ấy sẽ được tặng cuốn sách có giá trị 2 trong nhóm một, 4 trong nhóm hai, và không có quyển sách nào được tặng trong nhóm ba vì nhóm này chỉ có 1 quyển.
Cô bán hàng là một người tốt bụng vì vậy cô ấy luôn muốn mỗi khách hàng trả ít tiền nhất có thể.
Yêu cầu: Cho giá các quyển sách, hãy giúp cô bán hàng sắp xếp các quyển sách vào các nhóm sao cho tổng số tiền khách hàng phải trả là ít nhất có thể. Chú ý mỗi nhóm có ít nhất 1 quyển và nhiều nhất 3 quyển.
Dữ liệu vào: đọc từ tệp MUASACH.INP
- Dòng 1 là số nguyên N (1 ≤ N ≤ 105) – là số sách khách hàng mua;
- N dòng tiếp theo mỗi dòng ghi một số nguyên Ci (1 ≤ Ci ≤ 105) – là giá mỗi quyển sách.
Dữ liệu ra: Ghi ra tệp MUASACH.OUT: Một số nguyên duy nhất là giá tiền nhỏ nhất mà khách hàng phải trả.
Ví dụ:
[TBODY]
[/TBODY]
Một lời quảng cáo chào hàng trong một hiệu sách “mua 3, tặng 1, trả tiền 2”. Khách hàng được thông báo là khi mua ba quyển sẽ được tặng một quyển có giá rẻ nhất trong ba quyển đó. Tất nhiên, khách hàng có thể mua nhiều sách và phụ thuộc vào việc sắp xếp các quyển sách vào mỗi nhóm ba quyển để được miễn phí quyển có giá rẻ nhất trong nhóm đó.
Ví dụ: Khách hàng lấy 7 quyển sách có giá trị lần lượt là 10, 3, 2, 4, 6, 4, 9. Nếu các quyển sách này được sắp thành nhóm: (10, 3, 2), (4, 6, 4) và (9) thì khách hàng ấy sẽ được tặng cuốn sách có giá trị 2 trong nhóm một, 4 trong nhóm hai, và không có quyển sách nào được tặng trong nhóm ba vì nhóm này chỉ có 1 quyển.
Cô bán hàng là một người tốt bụng vì vậy cô ấy luôn muốn mỗi khách hàng trả ít tiền nhất có thể.
Yêu cầu: Cho giá các quyển sách, hãy giúp cô bán hàng sắp xếp các quyển sách vào các nhóm sao cho tổng số tiền khách hàng phải trả là ít nhất có thể. Chú ý mỗi nhóm có ít nhất 1 quyển và nhiều nhất 3 quyển.
Dữ liệu vào: đọc từ tệp MUASACH.INP
- Dòng 1 là số nguyên N (1 ≤ N ≤ 105) – là số sách khách hàng mua;
- N dòng tiếp theo mỗi dòng ghi một số nguyên Ci (1 ≤ Ci ≤ 105) – là giá mỗi quyển sách.
Dữ liệu ra: Ghi ra tệp MUASACH.OUT: Một số nguyên duy nhất là giá tiền nhỏ nhất mà khách hàng phải trả.
Ví dụ:
MUASACH.INP | MUASACH.OUT |
4 3 2 3 2 | 8 |
6 6 4 5 5 5 5 | 21 |