题目描述

在一条数轴上有 N 家商店，它们的坐标分别为 A1∼ANA_1∼A_N。

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

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

原题链接：AcWing 104. 货仓选址

思路

  1. 假设我们现在已经将这些商店在数轴上排列好了位置并且根据他们的相对位置编好号
  2. 我们将 A1A_1 与 ANA_N 放在一起分析，要在数轴上选取一个点让这个点到 A1A_1 和 ANA_N 的距离之和最小，那么这个点一定是在 [A1, AN][A_1,\ A_N] 这段距离之间，并且可以是这个区间上的任意一个值
  3. 同样的我们将 A2A_2 与 AN−1A_{N-1} 放在一起分析，得到这个点必须在 [A2, AN−1][A_2,\ A_{N-1}] 这个区间内，以此类推
  4. 最终，我们可以找到这段距离上的中间点（中位数）若这时这个中间值是一个点即N为奇数，那么这个点就是 AN/2A_{N/2} ；若此时这个中间值是两个点即N为偶数，那么我们可以任意选择 [AN/2, AN/2+1][A_{N/2},\ A_{N/2+1}] 区间内的一个点，为了统一我们选择 AN/2A_{N/2} 这个特殊的边界点；

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100010;

int n, a[N];

int main(){
    cin>>n;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    sort(a, a+n);
    
    int ans = 0;
    for(int i = 0; i < n; i++) ans += abs(a[i]-a[n/2]);
    
    cout<<ans;
    
    return 0;
}