思路

中位数就是最优解(取a,b之间随便一个数，到a,b之间代距离都是最小的)

相关题目

1.从一维扩展到二维（三分）
2.从三维扩展到d维（模拟退火）

方法一 $O(nlogn)$

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int const N=100010;
int num[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>num[i];
    sort(num,num+n);
    int cos=0;
    for(int j=0;j<n;j++)
    cos+=abs(num[j]-num[n/2]);

    cout<<cos<<endl;
    return 0;
}

方法二

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int const N=100010;
int num[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>num[i];
    sort(num,num+n);
    int cos=0;
    for(int j=0;j<n;j++)
    cos+=num[j]-num[j/2];

    cout<<cos<<endl;
    return 0;
}

写法三 $O(n)$

*** 把排序换成 nth_element(数组，我们需要代中间值，数组代最后一个数)时间复杂度为n;

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int const N=100010;
int num[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>num[i];
    nth_element(num,num+n/2,num+n);
    int cos=0;
    for(int j=0;j<n;j++)
    cos+=abs(num[j]-num[n/2]);

    cout<<cos<<endl;
    return 0;
}