题目描述
在一条数轴上有 N 家商店,它们的坐标分别为 A1~AN。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。
为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
输入
4
6 2 9 1
输出
12
思路
- 选取数轴上上一个点到其他点的距离最小,若数轴上为2个点可以得在两点之间距离最短。所以取所有点的中间值作为货仓选点最近 所以先排序,在求中间值
res += abs(a[i] - a[n / 2]
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
// 绝对值不等式
/*在一个数轴上的某点到其他商店的距离最小
x整个数的中间确保为最小
*/
const int N = 100010;
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 << endl;
return 0;
}