题目描述

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

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

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

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm> 
using namespace std;
int main()
{
    long long n,min=1000000000,s,sum=0;
    long long a[100000];
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int j = 1;j<=n;j++)
    {
        for(int k = 1;k<=n;k++)
        {
            s=abs(a[k]-a[j]);
            sum+=s;
        }
        if(sum<min)
            min=sum;
        sum=0;
    }
    cout<<min;
    return 0;
}

//超时了，暴力不了。

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//将数组排序后取中间元素
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
    long long n,s=0,sum1=0,sum2=0,sum3=0,min;
    long long int a[100010];
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    if(n%2==0)                      //偶数
    {
        for(int j = 1;j<=n;j++)
        {
            s=abs(a[j]-a[n/2]);
            sum1+=s;
        }
        s=0;
        for(int k = 1;k<=n;k++)
        {
            s=abs(a[k]-a[n/2+1]);
            sum2+=s;
        }
        if(sum1>sum2)               //因为定义了min变量所以用min函数时候出错了 
            cout<<sum2;
        else
            cout<<sum1;
        return 0;

    }
    else                            //奇数
    {
        for(int l = 1;l<=n;l++)
        {
            s=abs(a[l]-a[n/2+1]);
            sum3+=s;
        }
        cout<<sum3;
        return 0;
    }
}