题解|《算法竞赛进阶指南》 货仓选址

题目描述
在一条数轴上有N家商店，它们的坐标分别为 A[1]~A[N]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入描述:
第一行一个整数N，第二行N个整数A[1]~A[N]。

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

思路：
这类问题都是：在数轴上选一点到其他点的距离最短，直接中位数就行了。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e+5;

int n;
int a[N];

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int z = n / 2;//中位数
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(a[z] - a[i]);
    }
    cout << ans << endl;
    return 0;
}