绝对值不等式问题,贪心的思想,比较直观
直接把货仓放在
- (商店个数是奇数),中点处
- (商店个数是偶数),中心区间上,比如四个商店1234,货仓放在第2个和第3个商店区间上就可以了,可以取到区间端点
C++ 代码
-
输入时,n个商店在坐标轴上的位置可能是乱序的,需要排序以保证第a[n/2]处于中心位置
-
商店坐标输入时,下标最好从0开始,否则会出现n/2并不是中点的情况。比如说从n=3,
n/2 == 1
,输入 a1 a2 a3, 则a[n>>1] = a[1],不是中点a2,所以还需要写成a[(n>>1)+1]
,排序也要写成sort(a,a+n+1)
;
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n,a[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n); //排序,保证n>>1是中点(或中点区间)
int res=0;
for(int i=0;i<n;i++){
res += abs(a[i]-a[n>>1]);
}
cout<<res;
return 0;
}