507. 货仓选址
时间限制：1000 MS 内存限制：64 MB
题目描述
# 货仓选址 ## 题目描述 在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1,A_2,\ldots,A_N$。 现在需要在数轴上建立一家货仓。每天清晨，都要从货仓向每家商店运送一车商品。 数轴上两点之间的距离为它们坐标之差的绝对值。请合理选择货仓的位置，使货仓到所有商店的距离之和最小，并求出这个最小值。 ## 输入格式 从文件 `warehouse.in` 中读入数据。 第一行包含一个整数 $N$，表示商店的数量。 第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示各家商店的坐标。 ## 输出格式 将结果输出到文件 `warehouse.out`。 输出一个整数，表示货仓到所有商店的距离之和的最小值。 ## 数据范围 - $1 \le N \le 100000$。 - $0 \le A_i \le 40000$。 - 所有坐标均为整数，坐标可以重复，输入不保证有序。 - 距离之和请使用 $64$ 位整数存储。 ## 样例输入 ``` 4 6 2 9 1 ``` ## 样例输出 ``` 12 ``` ## 样例说明 将货仓建在坐标 $2$ 处，距离之和为 $$ |6-2|+|2-2|+|9-2|+|1-2|=4+0+7+1=12。 $$ 这是距离之和的最小值。货仓的最优位置可能不唯一。 ## 运行限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。