AcWing 104. 货仓选址
题目描述
在一条数轴上有 N 家商店,它们的坐标分别为 A1~AN。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。
为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
贪心策略
-
对于一个数轴,当数轴上存在两个点时————a———b—————,ab的距离是n,选取某个点到两点的距离和最小,观察图可知,当存在a和b之间时(包含两边端点),其距离和为n
当选取点在ab之外时,距离和就会大于n; -
当一个数轴上许多点时,————a———b———c——d————e————,此种情况时,依旧像上面的思想考虑即选取满足在ae中距离和最小的点、bd中距离和最小的点和cc中距离最小的点,很明显,当选取的点在c点时,
距离和最小; -
那么当点数为偶数时怎么办,其实依旧同理1中的思想,选取中间两点之间的任意一点(包含端点)结果相等;
代码如下:
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=100000+10;
int a[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
int l=0;
for(int i=0;i<n;i++)
{
l+=abs(a[i]-a[n/2]);
}
cout<<l;
return 0;
}
代码比较好理解,这里就不做注释了