Hoài Linh Tinh và Chí Tài Tình dự định tiếp tục xây dựng một ngôi trường cho trẻ em nghèo. Thời gian tựu trường đang tới gần nên họ đang phải tìm cách thi công công trình một cách nhanh nhất.
Công việc yêu cầu các nhân công phải làm việc theo cặp. Do các công nhân có tốc độ làm việc không giống nhau nên khi ghép cặp hai công nhân có tốc độ làm việc lần lượt là a và b (a < b) (đơn vị tốc độ làm việc), cặp đôi đó sẽ làm việc theo tốc độ là a (làm việc theo tốc độ của công nhân có tốc độ chậm hơn).
Bạn được 2 danh hài nhờ giải quyết bài toán ghép cặp công nhân sao cho đạt được tốc độ làm việc tối ưu nhất. 2 danh hài sẽ cung cấp cho bạn danh sách tốc độ làm việc của các công nhân trong công trường, tốc độ làm việc của các công nhân được lưu dưới dạng số nguyên dương, biết rằng số lượng công nhân trong công trường là số chẵn.
Chương trình dưới đây đã nhập giúp bạn dữ liệu vào 1 mảng số nguyên chứa tốc độ làm việc của các công nhân và biến n chứa số lượng cặp công nhân trong công trường.
Hãy viết chương trình xuất ra màn hình tổng tốc độ làm việc tối đa có thể đạt được của các cặp công nhân trong công trường.
Ví dụ:
n = 2
speed = [13, 50, 14, 1]
Giả sử ta thử ghép các cặp công nhân: 13 với 50, 14 với 1
cặp 13 và 50 sẽ có tốc độ làm việc là 13
cặp 14 và 1 sẽ có tốc độ làm việc là 1
Vậy tổng tốc độ làm việc của các cặp là: 13 + 1 = 14
Bây giờ ta ghép theo 1 cách tối ưu nhất: 13 với 1, 50 với 14
cặp 13 và 1 sẽ có tốc độ làm việc là 1
cặp 50 và 14 sẽ có tốc độ làm việc là 14
Vậy tổng tốc độ làm việc của các cặp là: 1 + 14 = 15
Ta thấy cách ghép thứ 2 cho kết quả tốt nhất.
Vậy kết quả cần xuất ra màn hình:
15
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?