$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')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(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
",ans);
	return 0;
}