Xây dựng cửa xuống hầm
Hiện nay quỹ đất rất hạn hẹp nên con người xây dựng những công xưởng sản xuất ở dưới lòng đất. Công ty VinaHam có một xưởng sản xuất đặt ở dưới lòng đất, có \(n\) công nhân làm việc trong một dây chuyền sản xuất coi như trên một đường thẳng có tọa độ lần lượt là \(x_1, x_2, ...,x_n\). Để tiêt kiệm kinh phí Công ty chỉ xây dựng một cửa lên xuống. Bạn hãy xác định vị trí xây dựng cửa này để làm sao tổng khoảng các từ cửa đến tất cả các vị trí (tọa độ) là ngắn nhất.
Input
Dòng đầu chứa số nguyên \(n (1 \leq n \leq 10^5)\)
Dòng tiếp theo chứa \(n\) giá trị tương ứng với tọa độ của các nhân viên, các tọa độ có thể trùng nhau \(x_1, x_2, ...,x_n\) có giá trị tuyệt đối không vượt quá 10^9.
Output
Tổng khoảng cách nhỏ nhất được xác định của cửa lên xuống tới tất cả các vị trí
Ví dụ 1
Input
5
-3 -7 1 13 -4Output
25Ví dụ 2
Input
4
4 9 3 6Output
8Giải thích ví dụ 2: Xây cửa thoát hiểm tại tọa độ 5 khi đó tổng khoảng cách nhỏ nhất sẽ là \(|4-5| + |9-5| + |3-5|+|6-5| = 1+4+2+1=8\)
Comments
useful function : nth_element(v.begin(), v.begin() + n / 2, v.end());
Có một thuật toán O(n) để xác định trung vị