# 题目背景

在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1 - A_N$
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小

# 算法思路 --- 绝对值不等式

# 衍生出代码

c++

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 10;
int n, a[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);

    int res = 0;
    
	// 下标从1开始
    for (int i = 1; i <= n; i++)
        res += abs(a[n / 2 + 1] - a[i]);
	    // n为奇数时, n / 2 + 1 恰好为最中间那个
	    // n为偶数时, n / 2 + 1 为最中间两个的左边的那个   
	
	
	// 下标从0开始	
	/*
	for (int i = 0; i < n; i++)	cin >> a[i];
    sort(a, a + n);

    int res = 0;
    for (int i = 0; i < n; i++)
        res += abs(a[n / 2] - a[i]);
	    // n为奇数时, n / 2 恰好为最中间那个
	    // n为偶数时, n / 2 为最中间两个的左边的那个     
    */
    
    cout << res << endl;
    return;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

此时会存在一个非常奇妙的事情，将下标从 $0$ 开始时的 res += abs(a[n / 2] - a[i]); 里的 a[n / 2] 换成 a[i / 2] 也能 $AC$
由此我们可以推出一个结论
$\sum\limits_{i=0}^{n-1}|(a_i -a_{n/2})|$ $=$ $\sum\limits_{i=0}^{n-1}|(a_i -a_{i/2})|$

# 证明如下

上述做法进行了 $sort$ ，复杂度 $n log(n)$

# 进一步优化

利用 nth_element( ) ，可优化至复杂度 $O(n)$
nth_element() ，默认是求 区间第 $k$ 小

# 例如

cpp

a[9]={4, 7, 6, 9, 1, 8, 2, 3, 5};
nth_element(a, a + 2, a + 9);

// 使用后输出
// 1 2 3 5 4 8 9 6 7

将第三小的数放在

a[2]

nth_element(a, a + k, a + n)
此函数把下标为

k

的元素放在了正确位置，对其它元素并没有排序
但第

k

个元素，左边元素都小于等于它，右边元素都大于等于它

# 优化代码

cpp

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 10;
int n, a[N];

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

    nth_element(a, a + n / 2, a + n);

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

    cout << res << endl;
    return;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

贪心