Mô tả
Khu phố cổ Hội An nằm dọc theo một con đường mang tên Trần Phú. Để triển khai dự án Wi-Fi miễn phí cho du khách, thành phố quyết định lắp đặt một trạm phát sóng duy nhất tại một nhà dân dọc theo tuyến đường này. Mỗi căn nhà đều có tọa độ là một số nguyên trên trục số, đánh dấu vị trí của nhà. Khi trạm được đặt tại nhà có tọa độ x, chi phí phủ sóng cho một nhà ở vị trí p là |p - x| đơn vị cáp quang. Mục tiêu là chọn vị trí đặt trạm sao cho tổng chi phí cáp cho toàn bộ các nhà là nhỏ nhất có thể. Hãy giúp UBND thành phố tìm ra tổng chi phí nhỏ nhất đó.
Đầu vào
Dòng đầu tiên chứa số nguyên dương n là số lượng nhà trên tuyến đường. Dòng thứ hai chứa n số nguyên a1, a2, ..., an là tọa độ của từng nhà, các số cách nhau bởi khoảng trắng.
Đầu ra
In ra một số nguyên duy nhất là tổng chi phí cáp quang nhỏ nhất.
Ràng buộc
- 1 ≤ n ≤ 10^5
- -10^9 ≤ ai ≤ 10^9
- Tọa độ các nhà không nhất thiết phân biệt, có thể có nhiều nhà cùng tọa độ.
Ví dụ
Ví dụ 1
Đầu vào
5 1 2 3 4 5
Đầu ra
6
Giải thích Các nhà nằm ở vị trí 1, 2, 3, 4, 5. Nếu đặt trạm tại nhà có tọa độ 3 (giá trị trung vị), tổng khoảng cách Manhattan là |1-3| + |2-3| + |3-3| + |4-3| + |5-3| = 2 + 1 + 0 + 1 + 2 = 6. Đây là tổng chi phí nhỏ nhất có thể.
Ví dụ 2
Đầu vào
4 10 20 30 40
Đầu ra
40
Giải thích Khi số nhà là chẵn, mọi tọa độ nằm giữa hai nhà ở giữa (từ 20 đến 30) đều cho cùng một tổng chi phí nhỏ nhất. Ví dụ đặt tại vị trí 20: |10-20| + |20-20| + |30-20| + |40-20| = 10 + 0 + 10 + 20 = 40.