题目描述

在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

因为距离一定是一个单峰函数，要找最小值，考虑用三分

算法1

(三分法) $O(nlog(n))$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int a[N],n;
ll check(int x)
{
    ll res=0;
    for(int i=1;i<=n;i++)res+=abs(x-a[i]);
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    int l=a[1],r=a[n];
    while(l<r-1)
    {
        int midl=(l+r)/2;
        int midr=(midl+r)/2;
        if(check(midl)>check(midr))l=midl;
        else r=midr;
    }
    cout<<min(check(l),check(r));
    return 0;
}