AcWing 104. 货仓选址
原题链接
简单
作者:
潘瑞杰
,
2019-11-22 20:46:15
,
所有人可见
,
阅读 862
算法1
/*
这个题只是说把货仓建在坐标轴上,所以我选择的这个的货仓可以在坐标轴上的任意位置。
所以我只要把货仓建在所有店的中间位置,那么这个点到所有的商店的距离就是总和就是
最小的。
这里涉及到中位数的一个性质:
给定一个数列,中位数有这样的性质 :所有数与中位数的绝对差之和最小。
题目链接 :https://www.acwing.com/problem/content/106/
Author:RUCKYONE
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
const int maxn = 1e5 + 5;
int num[maxn];
int main(void) {
int n,sum,mid;
scanf("%d",&n);
sum = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d",&num[i]);
}
sort(num + 1,num + 1 + n);
if(n % 2 == 0) mid = (num[n / 2] + num[n / 2 + 1]) / 2;
else mid = num[n / 2 + 1];
for(int i = 1; i <= n; i ++) {
sum += abs(num[i] - mid);
}
printf("%d\n",sum);
return 0;
}