P10452 货仓选址

· · 题解

P10452 货仓选址 题解

题目链接

题目大意

在数轴上找一个点，使得这个点到其他所有点的距离之和最小。

题目分析

这是一道找规律的题目。

先来看样例，对于样例来说，地图如下图所示：

这时，观察可以发现，在 2 \sim 6 之间建一个仓库可以让总和距离最小。那么，这是为什么呢？

因为这时我们可以发现，这个点都在每组线段上，这样的话，我们选的点到这两个点之间的和就是以这两个点为端点的线段的长度。在高中，我们将其称之为绝对值三角不等式。

推广一下，为了使距离和最小，就是要让这个点在每两个点构成的线段上，此时满足这个点到这两个点的距离和最小。由于数轴上的点是有次序的，所以长度最大的线段一定包含长度最小的线段，所以最后我们只需要在长度最小的线段上任取一点即可满足贪心。特别地，当点数为奇数时，在中间点建一个仓库即可满足题目要求。

注意开始循环前需要排序。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, ans, a[maxn];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n / 2; i++)
        ans += (a[n - i + 1] - a[i]);
    cout << ans;
    return 0;
}