笔记
这道题是利用了数学中的绝对值不等式的思想,在一维中任取一点到两个点的距离之和最短的条件是,这个点位于两点之间的区间上
做法:
1.先将各个点按照位置进行排序
2.找到位置是中位数的点,并记录(偶数是两个点,选择哪个都可以)
3.计算各个点到这个点的距离之和,即我们所求的最短距离之和。
拓展:
1.一维扩展到二维:3167. 星星还是树
2.扩展到d维:需要用模拟退火算法(难度高)。
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1e6+10;
int a[N];
int main(){
int n,sum=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",a+i);
sort(a,a+n);//将各个点按照位置进行排序
for(int i=0;i<n;i++)sum+=abs(a[i]-a[n>>1]);//计算各个点到这个点的距离之和
printf("%d",sum);
return 0;
}