仓库选址
-
在数轴上有n家商店，求在数轴上选一个仓库，使得到每个商店的距离之和最小
-
求最值问题 f(x) = x1 - x + x2 - x + … + xn - x -
进行分组 (x1, xn), (x2, xn-1), … 偶数个点正好分，奇数个点就是最后那个点分成单独一组
-
f(x) = ( x1 - x + xn - x ) + ( x2 - x + xn-1 - x ) + … -
f(x) >= ( xn - x1 ) + ( xn-1 - x2 ) + … - 只要选择这些点的中间就可以了, 只要选择这些点的中值就可以了.
- 注意，由于建在中位数点与建在中位数区间的两个断点是一直的，所以，我们可以选择建在中位数区间的某个断点，即某个商店处即可。
-
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int t[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &t[i]);
}
sort(t, t + n);
int res = 0;
for (int i = 0; i < n; i++) res += abs(t[i] - t[n /2]);
printf("%d", res);
return 0;
}
