中位数定理的板子题
题解描述
先排一遍序,计数排序或者直接sort的都行的,前者明显速度快多了。
之后找出中位数,选择一个值,记录一下结果就 ok。
代码
(sort排序) $O(nlog(n))$
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5+55;
int a[maxn];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++ i) {
cin >> a[i];
}
sort(a, a+n);
int pos = a[n/2];
ll ans = 0;
for (int i = 0; i < n; ++ i) {
ans += abs(a[i]-pos);
}
cout << ans << endl;
return 0;
}