备战蓝桥杯：贪心算法之货仓选址
当我们货仓选址在最中间的时候，货仓到每家商店的距离最短
#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;
}