中位数就是最优解
相关题目
1、一维扩展到二维:3167. 星星还是树
2、*扩展到d维:需要用模拟退火算法
算法1 O(nlogn)
#include<iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int num[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>num[i];
sort(num,num+n);
int dis=0;
for(int i=0;i<n;i++) dis+=abs(num[i]-num[n/2]);
cout<<dis;
return 0;
}
写法2 O(nlogn)
#include<iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int num[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>num[i];
sort(num,num+n);
int dis=0;
for(int i=0;i<n;i++) dis+=abs(num[i]-num[i/2]);
cout<<dis;
return 0;
}