题目分析
设总距离为Distance
如果只有两个商店
设商店A,B 求货仓W位置
$$Distance=|W-A|+|W-B|$$
显然,只有当WareHouse建立在A,B之间的时候,Distance取最小值
无论warehouse建立在A左侧还是B右侧,都会超过建立在中间
如果只有三个商店
我们会发现,把Warehouse建立在precisely中间这个商店的位置会比建立在A、B之间或者建立在B、C之间要短
总结
我们可以得出,
原理
当商店个数n为偶数时,我们把所有商店一边从最左、一边从最右,依次两两分组,我们只要保证货仓位置在所有组的中间就可以保证在每组中Distance都是这组两个端点的距离——最短距离
当商店个数n为偶数时,仍然这样做,只不过最后一组是位于中点的那个商店
我们把货仓建在这个商店的位置即可
总距离Distance=所有组两端点的距离之和
暴力版本代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<math.h>
int main(void){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int start=a[0],end=a[n-1],sum=0,minv=0x3f3f3f3f;
for(int i=start;i<=end;i++){
sum=0;
for(int j=0;j<n;j++){
sum+=abs(i-a[j]);
}
minv=min(minv,sum);
}
cout<<minv;
}
优化版本代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<math.h>
int main(void){
int n;
cin>>n;
int a[n+1];
a[0]=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a,a+n+1);
int location,distance=0;
if(n%2) location=a[n/2+1];//奇数位于中点商店处
else location=a[n/2]+1;//偶数位于中间一组两个商店中间
for(int i=1,j=n;i<=n/2;i++,j--){
distance+=a[j]-a[i];
}
cout<<distance;
}