绝对值不等式
//来自算法基础课
f(x) = |x[1]-x| + |x[2]-x| + |x[3]-x| + ... +|x[n]-x|
这是一个绝对值不等式
求这个函数的最小值
f(x) = (|x[1]-x| + |x[n]-x|) + (|x[2]-x| + |x[n-1]-x|) + ... //分组的思想
我们取出其中一组 |x[1]-x| + |x[n]-x|
就是在x[1]和x[n]所在直线上找出一点x,使得这一点到两端点的距离和最小
这样可以看出x取在x[1]和x[n]之间比较优
此时原式==x[n]-x[1]
所以第一项的最小值就是( x[n]-x[1] )
所以第二项的最小值就是( x[n-1]-x[2] )
......
所以f(x) >= (x[n] + x[n-1] + x[n-2] + ... + x[mid]) - (x[1] + x[2] + x[3] + x[mid])
当且仅当x取到最中间的两个数之间的时候等号成立
也就是说,当x取到x[]序列的中位数的时候不等式取到最小值
所以,对于这道题来说
我们首先把所有商店的坐标排个序
然后找出中位数即可
如果是奇数个商店,那中位数就是最中间的商店
如果是偶数个商店,那中位数在最中间的两个商店之间,
取这两个商店的任意一个都是答案(因为是整形嘛)
CODE
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],ans,mid;
int main(){
scanf("%d",&n);
for(register int i=1; i<=n; i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
if(n&1) mid = n/2+1;
else mid = n/2;
for(register int i=1; i<=n; i++) ans += abs(a[mid]-a[i]);
printf("%d\n",ans);
return 0;
}