题目描述
数轴上有N家商店,坐标分别为A1、A2……An。
在数轴上建立一个货仓,求货仓到每家商店的距离和的最小值。
(货仓可以建立在商店上,也可以在数轴上)
样例
输入:
4
5 2 6 1
输出:
8
算法1
时间复杂度
$O(nlogn)$
思路
排序后求中位数算出最小值(类似408)
C++ 代码
#include <iosrteam>
#include <algorithm>
using namespace std;
const int N=100010;
int n,dis;
int a[N];
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(int i=0;i<n;i++)dis += abs(a[i]-a[n>>1]);
cout<<dis;
return 0;
}