$CH0501$ 货仓选址

链接

背景

来源暂缺， \(AcWing104/CH0501\)

题意

在一条数轴上有 \(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; }

转载于:https://www.cnblogs.com/Peter0701/p/11256010.html

相关资源：JAVA上百实例源码以及开源项目