分数: 300 分
问题陈述
高桥将要与 N 朋友们。
他的朋友位于数轴上,并且 i第一个朋友在坐标处 X_i (不同的好友可能在同一个坐标)。
高桥想要决定一个见面地点。如果他将集合地点设置为整数坐标 P 在数轴上,每个朋友都会前往那个位置。所有好友的出行距离之和称为“总出行距离”。也就是说,总行驶距离为 |X_1 - P| + |X_2 - P| + \cdots + |X_N - P|。请注意,高桥自己的行驶距离不包含在总行驶距离中。
Takahashi 希望通过选择来最小化总行驶距离 P 最佳,为了尽可能减轻朋友的负担。
查找总行驶距离的最小值。
约束
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq X_i \leq 10^9
- 所有输入均为整数。
输入
N X_1 X_2 \cdots X_N
- 第一行包含一个整数 N,代表好友数量。
- 第二行包含整数 X_1, X_2, \ldots, X_N 以空格分隔,代表每个好友的坐标。
输出
将总行进距离的最小值作为整数打印在单行上。
示例输入 1
3 1 2 10
示例输出 1
9
示例输入 2
4 0 0 5 9
示例输出 2
14
示例输入 3
10 -12 4 7 -3 0 9 9 15 -8 2
示例输出 3
65
示例输入 4
20 12 -5 30 7 7 -18 42 0 3 3 3 50 -1 9 -15 100 -40 8 21 21
示例输出 4
363
示例输入 5
1 -1000000000
示例输出 5
0