题目描述
货仓选址
算法1
利用sort函数
直接利用sort函数排序,求得中位数
时间复杂度
O(nlogn)
可优化到O(n) 优化的代码其实就是把求中位数这个排序换成求第k大数的模板代码
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100010;
int num[N];
int main(){
int number;
cin>>number;
for(int i = 0;i<number;i++)
cin>>num[i];
sort(num,num+number);
int ans = num[number/2];
long long res = 0;
for(int i = 0;i<number;i++){
res += abs(ans-num[i]);
}
cout<<res<<endl;
}