总结:
本题用贪心算法,利用数学坐标和不等式求最小值点来寻找答案
思路:
本题在一个数轴上求某一点距离其他所有点最近,本质是商店-货仓的绝对值的总和的不等式值
求最小。
第一步:先用sort排序将商店坐标从小到大排列到一个数组中。
第二步:判断n为奇数还是偶数,如果是奇数,则中间那个商店则为距离其他点最近点
如果是偶数,则在中间两点之间
样例
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int res;
int main(){
cin>>n;
for(int i = 1;i <= n;i ++){
scanf("%d",&a[i]);
}
sort(a,a+n+1);
int y=0;
for(int i = 1;i <= n;i ++){
if(n % 2 != 0){
y = a[(1 + n)/2];
}else {
y = (a[n/2] + a[n/2 + 1])/2;
}
int x = a[i] > y?a[i] - y:y - a[i];
res += x;
}
cout<<res;
return 0;
}