104. 货仓选址

https://www.acwing.com/problem/content/106/

这一眼看过去是个数学题,解方程即可
设个x为仓库地址,然后x-a[i]进行求和,枚举每个位置求最小总距离,复杂度有点高,过不了,但是可以试试

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int a[N];
int ans=1e9+10;
int maxn=-1,minn=40010;
int sum(int x)//x为货仓地址
{
    int s=0;
    for(int i=0;i<n;i++)
    {
        s+=abs(x-a[i]);
    }
    return s;
}
int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        maxn=max(maxn,a[i]);
        minn=min(minn,a[i]);
    }
    for(int i=minn;i<=maxn;i++)
    {
        ans=min(sum(i),ans);
    }
    cout << ans << endl;
    return 0;
}

结果显然是超时...

暴力不行,可以试试举例猜想,从一个地点开始,那么显然仓库就放在那个地点,
两个地点,那么显然仓库在两个地点之间最短
三个地点,可以试试在中位数,即中间那个地点建仓,结果是第一个到最后一个的距离
在第一个到第二个之前建仓,发现相比在中位数建仓的距离要多一段
那么三个地点的情况也全了,总结如图(感觉这种有点类似于三角形or向量的绝对值不等式的证明?)

严格的去证明:首先可以设每个商店点为Ai,仓库点为c,那么所求的最短距离就可以表示为:min( sum(Ai - c) )
即 |A1-c| + |A2-c| +..... |An-c|,使这个式子最小,求c值
对于一个这样的式子,可以[ 分组 ]合并
可以转换为:  ( |A1-c| + |An-c|) + ( |A2-c| + |A(n-1)-c| ) + .... + ( A中-c ) 
对于这样的已经合并的式子可以从几何意义上去证明(其实就是绝对值不等式)
在 |Ai-c| + |Aj-c| 这个子项上, 从数轴上看,显然c取i~j之前的值可以使式子最小,值即为Aj-Ai这段距离
因此,c只需要满足所有式子即可
对于最后一项,n为奇数,则最后一项为: |A中-c|
n为偶数,则最后一项为:( |A(n/2)-c| + |A(n/2+1)-c| ) ,
显然最后一项的范围为所有项的子集,那么只需要c满足最后一项,c就满足所有项,因此,对于任何情况,只需要c建在中点(或者两个中点之间,包括端点)即可满足距离最小
如此,得证,但是这里我们进行了一个比较 妙 的操作,没错,就是那个[分组],因为分了组,才有绝对值不等式的形式,才便于证明

code就很简单了,读入所有Ai后,进行排序(组成数轴那种形式),然后取中位数建仓,然后计算距离即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N];
int n;
LL s;
int main()
{
    cin >> n;
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    int c = a[n/2];
    for(int i=0;i<n;i++)
        s+=abs(a[i]-c);
    cout << s << endl;
    return 0;
}