数轴上多个点，求到每个点的距离之和最小值；

题目描述

在一条数轴上有 NN 家商店，它们的坐标分别为 A_1A1∼A_NAN。

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

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

输入格式

第一行输入整数 NN。

第二行 NN个整数 A_1A1∼A_NAN。

输出格式

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

样例

输入数据 1

4
6 2 9 1

Copy

输出数据 1

12

Copy

数据范围

1≤N≤1000001≤N≤100000

0≤A_i≤400000≤Ai≤40000

这题好像是一个经典的数学题，不知道具体叫啥。

1.比如AB两点

1. 取最大的点和最小的点，那个点应该在那中间；

2. 再取第二个和倒数第二大的点，那个点也应在中间；如下图，如果在C.D之间包含C.D点，距离应为（AB)+(CD)；如果在C.D外，如n点就多加了（nc）这段。

3. 所以取最大和最小之间的点，

取第二和倒数第二之间的点，

取第三和倒数第三之间的点，

.......

所以应取的点为中位点。（取之间的点时候当然，两端点也可以取）

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

int main() {

int n;

cin >> n;

int a[n];

for(int i=0;i<n;i++){

cin >> a[i];

}

sort(a,a+n); //排序

int p=(n-1)/2; // 找中位数；

int ans=0;

for(int i=0;i<n;i++){

ans+=abs(a[p]-a[i]);

}

cout << ans;

return 0;

}