备战蓝桥杯：贪心算法之货仓选址

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

#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; }