AcWing 104. 货仓选址
原题链接
简单
作者:
凪
,
2021-02-05 12:59:39
,
所有人可见
,
阅读 251
题目描述
取中位数
算法1
$O(nlogn)$
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1000010;
int n, q[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
sort(q, q + n);
int res = 0;
for(int i = 0; i < n; i ++) res += abs(q[i] - q[n / 2]);
cout << res << endl;
return 0;
}
算法2
$O(nlogn)$
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1000010;
int n, q[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
sort(q, q + n);
int res = 0;
for(int i = 0; i < n; i ++) res += q[i] - q[i / 2];
cout << res << endl;
return 0;
}