题目描述

关系

3167-星星还是树

内容

在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1\sim A_N$。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数 $N$。

第二行 $N$ 个整数 $A_1\sim A_N$。

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

$1\le N\le 100000$,
$0\le A_i\le 40000$

输入样例：

4
6 2 9 1

输出样例：

12

问题分析

最初思路

思路分析

n 是奇数选中位数，n 为偶数选在两个数之间（其实就是中位数）。

公式推导

注意几个关键点：

• $|x-a|+|x-b|⩾|a-b|$；当 x 位于 ab 之间的的时候才可以取到等号；
• 对上式等号成立的条件进行推广，对于 n 的点，只有当 x 位于所有所有点之间才可以取得最小值，也就是取中位数；

执行流程设计

总结

• 利用 nth_element() 方法可以实现在 $O(n)$ 的复杂度找到第 k 大的数；

代码实现

解法 1

时间复杂度：$O(n\ast logn)$。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n;
int a[N];


int main() 
{
    cin >> n;
    
    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[i] - a[n/2]);
    
    cout << res;
    
    return 0;
}

解读：

• 将 res 的计算改为 for (int i = 0; i < n; i++) res += abs(a[i] - a[i/2]);；

解法 2-nth_element

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n;
int a[N];


int main() 
{
    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;
    
    return 0;
}