题目描述
在一条数轴上有 N 家商店,它们的坐标分别为 A1~AN。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。
为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数N。
第二行N个整数A1~AN。
输出格式
输出一个整数,表示距离之和的最小值。
数据范围
1≤N≤100000,
0≤Ai≤40000
样例
输入
4
6 2 9 1
输出
12
方法一(排序)
只需要简单的快排取中位数即可。
时间复杂度
O(nlogn),其中n为数组大小
C++ 代码
#include<bits/stdc++.h>
using namespace std;
//方法①
//采用快排的方式确定中位数,时间复杂度为O(nlogn);
int main(){
std::ios::sync_with_stdio(false);
int n;
cin>>n;
int num[n];
for(int i=0;i<n;i++)cin>>num[i];
sort(num,num+n);
int k=(0+n-1)/2;
long long sum=0;
for(int i=0;i<n;i++){
sum+=abs(num[i]-num[k]);
}
cout<<sum<<endl;
return 0;
}
方法二 (二分)
该方法是通过二分来找到解,思想就是我们在可能的解空间内二分,在每个二分的值下验证是不是恰好有(n+1)/2个元素是大于等于该值的,如果是,则该值就是货仓应该建立的位置,否则继续二分,直到搜索到的解满足条件为止。
时间复杂度
时间复杂度是O(nlogC)的,其中C是指数组元素中的极差大小。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
int n;
cin>>n;
int num[n];
for(int i=0;i<n;i++)cin>>num[i];
int l=0;
int r=100000;
for(;l<=r;){
int m=(l+r)/2;
int count=0;
for(int i=0;i<n;i++)if(num[i]-m>=0)count++;
if(count<(n+1)/2)r=m-1;
else l=m+1;
}
long long ans=0;
for(int i=0;i<n;i++)ans+=abs(num[i]-l+1);
cout<<ans<<endl;
return 0;
}