题目描述
在一条数轴上有 N 家商店,它们的坐标分别为 A1∼AN。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。
为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
样例
输入样例:
4
6 2 9 1
输出样例:
12
贪心算法
f(x)=|x-x1|+|x-x2|+......+|x-xn-1|+|x-xn|
将xi分组,x1和xn一组,x2和xn-1一组......
即求每组|x-x1|+|x-xn|
的最小值,也就是在区间x1~xn
之间取一个x,答案既可得到最小值,若x在区间外,答案会比x取在区间内的结果大
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=100010;
int a[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
sort(a,a+n);
int res=0,mid=n/2 ;
for(int i=0;i<n;i++)
{
if(n%2)
res+=abs(a[mid]-a[i]);
else
res+=abs(a[mid]-a[i]);
}
cout<<res<<endl;
return 0;
}