首先,我们会想到在所有距离中取平均数,让货仓到每家商店的距离和最小。
然后,你就可以喜提20分了
这时,我们就可以考虑从 [min^{n}_{i=1}a_i,max^n_{i=1}a_i] 中枚举,找最小距离和。
然后你就会发现,AC了。
核心代码如下:
for(int i=a[0];i<=a[n-1];i++){
for(int j=0;j<n;j++)sum+=abs(i-a[j]);
ans=min(ans,sum);
sum=0;//※※※这一步千万别漏掉
}