← 返回题目列表

AtCoder · awc0053_b

B. 集合地点

中文机器翻译题面 查看原题

分数: 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