题解 0x05 基本算法-排序 货仓选址

直观的想，假设我们将货仓建在第k个商店的坐标上，那么货仓左边有 k - 1 个商店，右边有 n - k - 1 个商店，当我们将货仓向右移动一个单位，那么货仓距离左面所有的商店的距离就会增加一个单位，距离右面所有的商店的距离会减少一个单位，所以应当使左右商店的个数相同， k-1 = n-k-1, 那么k=n/2, k就是整个序列中位数的位置。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);

    int spc = a[n >> 1];
    int res = 0;

    for (int i = 0; i < n; i++)
        res += abs(a[i] - spc);

    cout << res << endl;
}