python/TangDou/AcWing/104.md

##AcWing 104. 货仓选址

一、题目描述

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

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

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

输入格式 第一行输入整数 N。

第二行 N 个整数 A_1∼A_N。

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

数据范围 1≤N≤100000,0≤A_i≤40000

输入样例：

4
6 2 9 1

输出样例：

12

二、解题思路

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

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

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

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

结论

• 下标从0开始:获取中位数：\large \displaystyle a[n/2]
• 下标从1开始:获取中位数：\large \displaystyle a[n/2+1]

总结

中位数，不一定非得建设到绝对的平均数，在中间范围内的任何一个点都是一样的。

三、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int n, res;
int a[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n); // 注意下标从0开始

    for (int i = 0; i < n; i++) res += abs(a[i] - a[n / 2]);
    printf("%d", res);
    return 0;
}