绝对值不等式

4.绝对值不等式

AcWing 104.货仓选址

实现思路：

假设n个商店在数轴上的坐标依次为：x1，x2，x3，…，xn

设仓库的位置为x，则总的距离为

1

f(x) = |x1 - x| + |x2 - x| + ... + |xn - x|

我们要求解的就是f(x)的最小值。

我们可以先进行一下分组，1和n为一组，2和n-1为一组…

1

f(x) = (|x1 - x| + |xn - x|) + (|x2 - x| + |x_n-1 - x|) + ....

单独看一组，任意一组都可以写成形如|a - x| + |b - x|的形式，a和b是已知的常数，x是未知数。假设a < b，则容易知道，当x取值在[a,b]这个区间内时，上面的表达式取得最小值b - a，而x取值只要落在[a,b]区间外，则上面的表达式的值一定是大于b - a的。

由此可知，对于分组1和n，只要x取值在[x1,xn]这个区间内，就能使|x1 - x| + |xn - x|取得最小值xn - x1。同理，对于|x2 - x| + |x_n-1 - x|，只要x取值在[x2,x_n-1]区间内，就能使这个部分取得最小值x_n-1 - x2…容易得出，只要取所有分组的区间的交集即整个区间的中间点，能使总的f(x)最小。即，当n为偶数时，x只要落在最中间2个点之间即可；当n为奇数时，x只需要落在最中间的那个点上即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int n,a[N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    int res=0;
    for(int i=0;i<n;i++) res+=abs(a[i]-a[n/2]);
    cout<<res;
    return 0;
}