思路
中位数即是最优解
相关题目
- 一维扩展到二维:3167. 星星还是树三分法
-
- 扩展到多维(d维):模拟退火算法
解法一:C++ $O(nlogN)$
#include <iostream>
#include <algorithm>
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]);
}
cout << res << endl;
return 0;
}
解法二:C++ nth_element $O(n)$
#include <iostream>
#include <algorithm>
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);
int res = 0;
for(int i = 0;i<n;i++){
res += abs(a[i] - a[n/2]);
}
cout << res << endl;
return 0;
}