AcWing 104. 货仓选址
原题链接
简单
作者:
月下邂逅
,
2024-04-24 19:42:28
,
所有人可见
,
阅读 2
C++ 代码
/*
排序取每个数到中位数的平均值即可,假设仓库左边有i个商店,右边有j个商店,仓库右移一格时总距离+i-j,左移一格时总距离-i+j,若
abs(i-j)!=abs(j-i),说明可以优化,所以i=j时仓库位置最优,所以仓库的选址应该在中位数上,偶数个时在[a[n/2],a[n/2+1]]内即可
//平方距离取平均数,距离取中位数
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N];
int main()
{
int n,distance=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
distance+=abs(a[i]-a[n/2]);//等价于a[i]-a[i/2]
}
printf("%d",distance);
return 0;
}