Xây dựng cửa xuống hầm

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

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à x1,x2,...,xn. Để 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≤n≤105)

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 x1,x2,...,xn 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

Copy
5
-3 -7 1 13 -4

Output

Copy
25

Ví dụ 2

Input

Copy
4
4 9 3 6

Output

Copy
8

Giả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

tichpx

Comments


  • 0
    kienduy1221  commented 45 days ago

    Tổng khoảng cách sẽ nhỏ nhất khi số đó chính là số trung vị


  • 0
    cotyey  commented on Nov. 5, 2019, 6:26 a.m.

    useful function : nth_element(v.begin(), v.begin() + n / 2, v.end());


    • 0
      TICHPX  commented on Nov. 5, 2019, 9:37 a.m.

      Có một thuật toán O(n) để xác định trung vị