题解：P10452 货仓选址

hema5177 · 2024-05-16 18:37:09 · 题解

思路

要使仓库到商店的距离之和最小，把仓库设在一个商店的位置至少能使一个商店到仓库的距离为 0，是最佳的策略。因为选在不是商店的区域都可能会有距离上不必要的浪费。而选择作为仓库的商店处于这N家商店的中间，距离之和就会最小。因为所有商店到这家商店的距离的数值之差都会比较小。排序并选择中间那个商店作为仓库即可。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,a[100001],sum;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) sum+=abs(a[n/2]-a[i]);
    cout<<sum;
}