一个 $\mathcal{O}(n)$ 的算法

优化

贪心思路这里就不再讲了，主要优化点是不需要排序找到最中间的点，使用找到第 $x$ 个点的（排序）模型（算法实现类似快速排序）即可，其中，C++ 包含这样一个封装好的函数 nth_element(begin,nth_iterator,end).

代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+10;
int a[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    nth_element(a+1,a+n/2+1,a+n+1);
    int x=a[n/2+1],ans=0;
    for(int i=1;i<=n;++i)
        ans+=abs(a[i]-x);
    cout<<ans;
    return 0;
}