题目描述

blablabla

样例

blablabla

方法：采用计数排序

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=200010;
int a[N];
int res[N];

int main() {
    int n;
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=0;i<n;i++) cin>>a[i];
    int maxv=*max_element(a,a+n);
    int minv=*min_element(a,a+n);
    int countlen=maxv-minv+1;
    int count[countlen];
    memset(count,0,sizeof count);
    for (int i=0;i<n;i++) {
        count[a[i]-minv]++;
    }
    int index=0;
    for (int i=0;i<countlen;i++) {
        while (count[i]>0) {
            res[index++]=i+minv;
            count[i]--;
        }
    }
    int sum=0;
    for (int i=0;i<n;i++){
        sum+=abs(res[i]-res[n/2]);
    }
    cout<<sum<<endl;
    return 0;
}