货仓选址

货仓选址

在一条数轴上有 $N$ 家商店,它们的坐标分别为 $A_1…A_N$。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。

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

输入格式

第一行输入整数$N$。

第二行$N$个整数$A_1…A_N$。

输出格式

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

数据范围

$1≤N≤100000$

输入样例

1
2
4
6 2 9 1

输出样例

1
12

解析

无代码,只放证明

假设仓库建在最优位置(必需有这个前提)时,左边有 $a$ 个商店,那么右边就有 $n - a$ 个商店,左边商店距离仓库的位置之和为 $p$ ,右边的商店距离仓库的位置之和为 $q$ 可得 $p + q$ 为所有商店到仓库的最小距离之和

现在将仓库向左移 $x$,可得
$p - ax + q + (n-a)x$
$ = p - ax + q + nx - ax$
$ = p + q + (n - 2a)x $

因为仓库之前是设在最优位置,所以 $n - 2a ≥ 0$ ,如果不满足这个条件,那么就和我们仓库建在最优位置的条件产生冲突,即 $p + q$ 就不是我们的所有商店到仓库的距离之和最小了。

此时,当 $a = \frac{n}{2}$ 时,得到最优答案。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!