服装公司网站设计_网站建设服务公司有用吗_南京百度网站推广_成都seo优化排名推广

当我们货仓选址在最中间的时候，货仓到每家商店的距离最短

#include <iostream>
#include <cstdlib>
#include <algorithm>
typedef long long LL;
using namespace std;
int n;
const int N = 1e5+10;
LL a[N];
int main()
{cin >> n;for(int i = 1;i<=n;i++) cin >> a[i];sort(a+1,a+1+n);LL ret= 0;for(int i = 1;i<=n;i++) ret+=abs(a[i]-a[n/2]);cout << ret << endl;return 0;
}

贪心策略证明：

我们首先需要直到一个绝对值不等式的公式

|a-x|+|b-x| >= |a-b|

我们的代码也可以直接用这个公式来算

#include <iostream>
#include <cstdlib>
#include <algorithm>
typedef long long LL;
using namespace std;
int n;
const int N = 1e5+10;
LL a[N];
int main()
{cin >> n;for(int i = 1;i<=n;i++) cin >> a[i];sort(a+1,a+1+n);LL ret= 0;for(int i = 1;i<=n/2;i++) ret+=abs(a[n-i+1]-a[i]);cout << ret << endl;return 0;
}