AcWing 104. 货仓选址
原题链接
简单
作者:
随风随心
,
2021-01-12 22:45:18
,
所有人可见
,
阅读 266
就是第k大的数的变形
不过要注意第k大的数是从1开始,因此中间的数是(n+1)/2;
//将整个数组分为两半即可
#include <iostream>
using namespace std;
const int N = 100000+10;
int n;
int q[N];
int quick_sort(int l, int r, int k){
if(l == r) return q[l];
int x = q[l], i = l - 1, j = r + 1;
while(i < j){
while(q[++i] < x);
while(q[--j] > x);
if(i < j) swap(q[i], q[j]);
}
int s1 =j - l +1; // or j -l +1
if(k <= s1) quick_sort(l, j, k);
else quick_sort(j + 1, r, k- s1);
}
int main(){
cin>>n;
for(int i =0 ; i < n ; i++){
scanf("%d" ,&q[i]);
}
int mid = quick_sort(0,n-1,(n+1)/2);
int sum =0;
for(int i = 0;i<n;i++){
sum += abs(mid - q[i]);
}
printf("%d" , sum);
return 0;
}