题目描述
在一条数轴上有N家商店,它们的坐标分别为 A1~An。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。
为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数N。
第二行N个整数A1~An
输出格式
输出一个整数,表示距离之和的最小值。
数据范围
1≤N≤100000
样例
输入
4
6 2 9 1
输出
12
算法1
同样是中位数思想 但是并不需要找出这个中位数
sort排序之后 直接最后一个减去第一个,倒数第二个减去第二个.......
以此类推到n/2
C++ 代码
#include<iostream>
#include<algorithm>
#define N 1000010
using namespace std;
int n;
int a[N];
int main(){
cin>>n;
long long num=0;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int i=0,j=n-1;
while(i<j){
num+=a[j--]-a[i++];
}
cout<<num<<endl;
return 0;
}
牛逼,比中位数好理解很多!!!仔细一想就懂了