【中位数】 货仓选址

题意

传送门
一条数轴上有\(N\)家商店，坐标分别为\(A_{1}\sim A_{N}\)，建一个货仓，求货仓建在哪里使得货仓到各个商店距离之和最小

数据范围

\(1 \leq N \leq 100000\)

题解

先将\(A_{1}\sim A_{n}\)排序设货仓在坐标\(x\)处，\(x\)左侧有\(P\)个，右侧有\(Q\)个，

• 若\(P<Q\)则当货仓右移一个单位，距离之和会变小\(Q-P\)，
• 同理\(P>Q\),则左移会使变小\(P-Q\)，

故当\(P=Q\)时最优，奇数在\(A_{n+1>>1}\)处最优，偶数在$A_{n>>1} \sim A_{n>>1 +1} $都是最优的

Code

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
const int N=1e5+10;
int n,ans;
int a[N];
int main(){
    scanf("%d",&n);
    rep(i,1,n+1) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int p;
    if(n&1) p=a[n+1>>1];
    else p=a[n>>1];
    rep(i,1,n+1)  ans+=abs(a[i]-p);
    printf("%d\n",ans);
}

【中位数】 货仓选址

原文：https://www.cnblogs.com/hhyx/p/13287098.html