背景

题意

在一条数轴上有 \(n\) 个点，确定一个位置使得各点到该点的距离之和最小。输出各点到该点的距离之和。

解法

显然，确定的点位置不可能在最左边点的左边或者是最右边点的右边，这两种安排都比最左边点与最右边点之间更劣。

在最左边点与最右边点之间任取一个位置，则它的左边有 \(p\) 个点，右边有 \(q\) 个点。当 \(p < q\) 时，将该点向右移动一个单位，则距离之和减少了 \(q-p\) 个单位；当 \(p > q\) 时，将该点向左移动一个单位，则距离之和减少了 \(p-q\) 个单位。只有 \(p = q\) 时距离之和才能最小。即确定的点处于排序后左边点和右边点一样多的位置（中位数）时距离之和最小。

接下来对于 \(n\) 分奇偶性讨论即可。 \(n\) 为偶数时，确定的点在第 \(\frac{n}{2}\) 个点和第 \(\frac{n}{2}+1\) 个点之间；而 \(n\) 为偶数时，确定的点在第 \(\frac{n+1}{2}\) 个点处。

代码

$View$ $Code$

//省略头文件using namespace std;inline int read(){    int ret=0,f=1;    char ch=getchar();    while(ch>'9'||ch='0'&&ch<='9')    {        ret=(ret<<1)+(ret<<3)+ch-'0';        ch=getchar();    }    return ret*f;}int n,a[100005],pos;long long ans;int main(){    n=read();    for(register int i=1;i<=n;i++)        a[i]=read();    sort(a+1,a+n+1);    if(n&1)        pos=a[(n+1)>>1];    else        pos=a[n>>1];    for(register int i=1;i<=n;i++)        ans+=abs(a[i]-pos);    printf("%lld\n",ans);    return 0;}