题目描述
在一条数轴上有N个点,A1~AN。
寻找一个点,使得n个点到该点的距离和最小
思路
首先看一下当n=2的情况
有不等式 |x-a|+|x-b|>=|a-b|(当且仅当x在线段ab上时取等)
当n=2时,符合条件的点x的坐标应该在[a,b]中
根据不等式可以类比:
|x-a1|+|x-a2|+...|x-an|
=(|x-a1|+|x-an|)+(|x-a2|+|x-an-1|)+...
>=|a1-an|+|a2-an-1|+...
每一个等号成立的条件都是x在范围之间
所以得出结论:
当n为奇数时,x为n的中位数
当n为偶数时,x取中间两个数之间任意数都可
参考代码
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int a[1000005];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<=n;i++)
ans+=fabs(a[(n+1)/2]-a[i]);
printf("%d",ans);
}