做题思路
* 中位数就是最优解 *
1.开一个数组 a[],存放各个商店的位置。
2.对数组a 排一下序。
3.若商店数 n 为奇数 , 货仓位置 为 商店数的中位数 :
若商店数 n 为偶数 , 货仓位置 为 中间两个数的任意一个
表示为 a[n/2];
涉及的核心知识点
绝对值不等式
|a-x|+|b-x|>=|a-b|
相关题目
- 一维扩展到二维: 3167. 星星还是树
用三分,证明是凸函数。 -
- 扩展到 n维 :可以用 模拟追火算法。
代码
写法 一 $O(nlogn)$
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
int a[N];
int main(){
cin>>n;
for(int i= 0;i<n;i++) cin>>a[i];
sort(a,a+n);
int res=0;
for(int i=0;i<n;i++) res+=abs(a[i]-a[n/2]);// a[i/2] 也对。
cout<<res<<endl;
return 0;
}
写法 二 $O(nlogn)$
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
int a[N];
int main(){
cin>>n;
for(int i= 0;i<n;i++) cin>>a[i];
sort(a,a+n);
int res=0;
for(int i=0;i<n;i++) res+=abs(a[i]-a[i/2]);
cout<<res<<endl;
return 0;
}
写法 三 $O(n)$
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
int a[N];
int main(){
cin>>n;
for(int i= 0;i<n;i++) cin>>a[i];
nth_element(a,a+n/2,a+n);//nth_element(迭代器首,排位是几位的,迭代器尾的下一个);
int res=0;
for(int i=0;i<n;i++) res+=abs(a[i]-a[n/2]);
cout<<res<<endl;
return 0;
}