每日一题：货仓选址

题意

在数轴上找到一个点，使得到其余 $n$ 个点距离之和最小。$(n \in [1, 1e5])$

Solution

考虑绝对值不等式：

当只有两个点 $a, b$ 时，有 $|a - x| + |b - x| >= |a - b|$，为了满足 $|a - x| + |b - x| = |a - b|$ 关系，$x$ 必须选在 $a,b$ 两点之间。

拓展为 $n$ 个点，距离为 $|a[1] - x| + |a[2] - x| + … + |a[n - 1] - x| + |a[n] - x|$，收尾两两分组有 $(|a[1] - x| + |a[n] - x|) + (|a[2] - x| - |a[n - 2] - x| + …)$，两两应用绝对值不等式，$x$ 的位置必须满足在各个对应区间里。

得出结论：当 $n$ 为奇数时，$x$ 位置为中间那个点（因为刚好分组多出单独一个，满足最小性则必须将 $x$ 的位置选择为那个点，距离刚好为 $0$）；当 $n$ 为偶数时，$x$ 位置为中间两个点之间的任意位置都可。

Code

#include <bits/stdc++.h>
using namespace std;
int n, res, a[100005];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n; i++) res += abs(a[i] - a[n >> 1]);
    cout << res << endl;
    return 0;
}