题目描述

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

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

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

输入格式

第一行输入整数N。

第二行N个整数A1
~AN
。

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

1≤N≤100000

输入样例：

4
6 2 9 1

输出样例：

12

【思路】：三分，通过题意可知这个肯定是一个单峰函数
那么我们肯定可以通过简单的三分来分出一个最小值的点
然后使用计算函数f(x)，来得出答案
运行时间（89 ms）

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int arr[MAXN];
int n;
/**
使用三分来尝试一下
**/
double f(double x)
{
    double ans = 0;
    for(int i = 0; i < n; i ++)
    {
        ans += fabs(x - arr[i]);
    }
    return ans;
}
double finds(double ll, double rr)
{
    double l = ll;
    double r = rr;
    double mid, mids;
    while(l + 1e-5 < r)
    {
        mid = (l + r) / 2.0;
        mids = (mid + r) / 2.0;
        if(f(mid) < f(mids))
        {
            r = mids;
        }
        else
        {
            l = mid;
        }
    }
    return l;
}
int main()
{
    scanf("%d", &n);
    int maxs = 0;
    for(int i = 0; i < n; i ++)
    {
        scanf("%d", &arr[i]);
        maxs = max(arr[i], maxs);
    }
    double m = maxs * 1.0;
    double re = finds(0, maxs);
    printf("%.0f\n", f(re));
    return 0;
}