货仓选址问题

题目描述

在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1 \sim A_N$。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数 $N$。

第二行 $N$ 个整数 $A_1 \sim A_N$。

输出格式

输出一个整数，表示距离之和的最小值。

输入输出样例 #1

输入 #1

4
6 2 9 1

输出 #1

12

输入输出样例 #2

输入 #2

5
1 3 5 7 9

输出 #2

10

限制条件

• $1 \le N \le 100000$
• $0 \le A_i \le 40000$

样例解释 #1

商店坐标：$[6, 2, 9, 1]$

首先将坐标排序：$[1, 2, 6, 9]$

当 $N$ 为偶数时，货仓建在中间两个商店之间的任意位置都可以得到最小距离和。

选择货仓建在位置 $4$（在 $2$ 和 $6$ 之间）：

• 到商店 $1$ 的距离：$|4-1| = 3$
• 到商店 $2$ 的距离：$|4-2| = 2$
• 到商店 $6$ 的距离：$|4-6| = 2$
• 到商店 $9$ 的距离：$|4-9| = 5$

总距离：$3 + 2 + 2 + 5 = 12$

因此输出 $12$。

数学原理

将货仓建在所有商店坐标的中位数位置时，可以得到最小的总距离和。

具体来说：

1. 将商店坐标排序
2. 如果 $N$ 是奇数，货仓建在第 $\lfloor \frac{N}{2} \rfloor + 1$ 个商店的位置
3. 如果 $N$ 是偶数，货仓可以建在第 $\frac{N}{2}$ 和第 $\frac{N}{2} + 1$ 个商店之间的任意位置