原题链接: 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;
}