货仓选址 (每日一题)

原题链接: AcWing

题目描述:

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

输入格式

第一行输入整数 N。 第二行 N 个整数 A1∼AN。

输出格式

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

数据范围

1 ≤ N ≤ 100000, 0 ≤ Ai ≤ 40000

输入样例：

4
6 2 9 1

输出样例：

12

解题思路:

这道题是一个贪心问题，需要用到数学里的绝对值不等式，其实拆开来看就是一个求排序后数组中位数的差的题，因为要想距离这些商店都短，那么必然要在他们的距离之间寻求一个中位数，中位数有非常优秀的性质，比如说在这道题目中，每一个点到中位数的距离，都是满足全局的最有性，而不是局部最优性。

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 1;
int q[N], res, n;
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &q[i]);
    }
    sort(q, q + n); //排序
    for (int i = 0; i < n; ++i)
    {
        res += abs(q[i] - q[n / 2]); //统计和中位数之间的差
    }
    printf("%d", res);
    return 0;
}