货仓选址

思路分析

直觉上，我们也可以猜出来是将货仓建在最中央。所以我们先对货仓的坐标进行排序，然后将每一个货仓与中位数作差的绝对值求和即可

证明

首先我们对货仓进行编号，从距离小的开始编号。然后可以写出来距离的表达式，如上图所示

我们将最小和最大配成一组，它们的最小值，在两点之间取到。次小和次大的距离最小值也在它们之间取到。依次类推，最小值是最中间取得，并且取在最中间可以让每一组都是最小值。

奇数个点时候，货仓就在最中间的商店
偶数个点时候，货仓在最中间两个商店之间（含商店）

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int q[N];

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    sort(q, q + n); // 商店坐标升序排列

    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(q[i] - q[n / 2]);
    // 求出每一个商店和最中间的地方的距离

    printf("%d\n", res);

    return 0;
}