题目描述
在一条数轴上有 N 家商店，它们的坐标分别为 $A_1 … A_N。$
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数N。
第二行N个整数$A_1 … A_N。$
输出格式
输出一个整数，表示距离之和的最小值。
数据范围
$1≤N≤100000$
样例
输入样例：
4
6 2 9 1
输出样例：
12
排序+中位数
中位数有非常优秀的性质，比如说在这道题目中，每一个点到中位数的距离，都是满足全局的最有性，而不是局部最优性。
具体的来说，我们设在仓库左边的所有点，到仓库的距离之和为$p$,右边的距离之和则为$q$，那么我们就必须让$p+q$的值尽量小。
当仓库向左移动的话，$p$会减少$x$，但是$q$会增加$n-x$，所以说当为仓库中位数的时候,$p+q$最小。
还是同样的一句话，画图理解很重要。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N],n,i,ans,sum;
int main()
{
cin>>n;
for (i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);//排序
int sm=a[n/2+1];//中位数
for (i=1;i<=n;i++)
ans=ans+abs(a[i]-sm);//统计和中位数之间的差
cout<<ans;
return 0;
}
为什么要把仓库建在已有的商店上
如果我的商店坐标是1 3 3，那结果不应该是3吗？
结果是2
假设将货仓建在数轴上的某一点 P，那么货仓到商店 i 的距离就是 |Pi−Ai|，其中 |x| 表示 x 的绝对值。
因此，货仓到所有商店的距离之和就是
|P1−A1|+|P2−A2|+⋯+|PN−AN|
要使得这个距离之和最小，需要找到一个点 P，使得所有商店到点 P 的距离之和最小。
如果将所有商店的坐标按从小到大排序，那么最优的点 P 就是中间的那个商店的坐标。如果商店的数量是偶数，那么最优的点 P 就是中间两个商店坐标的平均值。
因此，可以将所有商店的坐标排序，然后找到中间的那个商店或者中间两个商店的平均值，就是最优的点 P。
但是偶数情况下，中位数下取整就行，到左边减少的距离和到右边增加的距离是相等的，所以直接取中位数=a[ n / 2 + 1]
你这不是答非所问吗？1 3 3如果仓库取3的话，移动距离为2，如果仓库取2的话，移动距离不是3吗？所以仓库取3更优吧？
输出结果是距离，是2
哦哦 我瞎了
为啥不是在3建仓库
就是在3建仓库
‘’当仓库向左移动的话，p会减少x’‘这句话是错的吧，应该是仓库左边有几个点就少几个x吧。
对，假设左边a个点那么左边距离为p-ax，右边距离为q+(n - a)x，总和为p+q+(n - 2*a)x，当a=n/2时，最佳为p+q
你这个说的也不对 应该是p+q+abs[(n-2a)x]，a=n/2时才能取最佳。
因为定义sum使用sm
可以理解成防作弊
什么是防作弊qaq
”最有性“是不是写错了
a[n/2+1] n是奇数，取的是中位数，n是偶数是取的是什么呢？
以样例举例，n为偶数时你会发现中间这两个点选取哪一个结果都是一样的
ans没初始化为0，是不是写错了啊
全局变量初始化为0
全局变量
如果是输入多个货仓怎么办
此代码CE
没有吧。。。
输入
3
2 6 10 时正确答案是8 而你的输出是12
n>>1|1 不等于 n/2+1 找到的不一定是这些数的中位数
emmmm 是不是应该加强一下数据Orz
是的,我以为我改掉了代码,看来ctrl键有点不好用了.
n>>1 | 1 相当于n/2+1吗？
偶数情况下等于
欧克
并不，例如当n=6时，n>>1 | 1等于3,而n/2+1等于4
满足n=4k或n=4k+1(k为自然数，不考虑负数)时满足吧..