python/TangDou/AcWing/104.md

##[$AcWing$ $104$. 货仓选址 ](https://www.acwing.com/problem/content/description/106/)

### 一、题目描述
在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1∼A_N$。

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

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


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

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

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

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

**输入样例：**
```cpp {.line-numbers}
4
6 2 9 1
```

**输出样例：**
```cpp {.line-numbers}
12
```

### 二、解题思路

![1.png](https://cdn.acwing.com/media/article/image/2021/03/24/64630_3f0d65b18c-1.png) 

假设仓库建在最优位置（必需有这个前提）时，左边有$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]$

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

### 三、实现代码
```cpp {.line-numbers}
#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;
}
```