题目描述
在一条数轴上有$N$家商店,它们的坐标分别为 $A_1$…$A_N$。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。
为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数$N$。
第二行N个整数$A_1…A_N$。
输出格式
输出一个整数,表示距离之和的最小值。
数据范围
$1\leq x\leq 100000$
输入样例:
4
6 2 9 1
输出样例:
12
算法1/1(排序+中位数)
这题显然是把货仓放到中位数上,证明:
设最终仓库在$X$点。在$X$点的左边有$a$个商店(包括自身),右边有$b$个商店(包括自身)。若$a\lt b$,每把商店往右移一位,距离之和减少$b-a$,说明有更优解,所以$a$不得小于$b$。若$a\gt b$,每把商店往左移一位,距离之和减少$a-b$,说明有更优解,所以$a$不得大于$b$。
综上,$a=b$为最优解,中位数 为最佳位置。
大致思路:
先将$a[1]$~$a[n]$排一下序
找到中位数,存至一个变量(我的程序里为x)
暴力算出总距离
举个例子:
4
6 2 9 1
排序:1 2 6 9
找中位数(偶数个数为中间两个数的平均数。其实取$a[n/2]$就行了,因为对$A$和$B$的大小关系没影响),中位数=$2$。
暴力算出:$|2-1|+|2-2|+|6-2|+|9-2|=12$
答案:$12$
时间复杂度$O(nlog_n)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
long long a[114514],n,x,s,i;
int main()
{
cin>>n;
for(i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
x=a[(n+1)/2];
for(i=1;i<=n;i++) s+=abs(a[i]-x);
cout<<s;
return 0;
}
额,这题不用考虑重叠吗
比如 3
1 2 3这样的测试数据是不是就不对了
不是$|1-2|+|2-2|+|3-2|$吗
我想多了,我以为有商店的地方就不能建仓库
哦哦
这题一点都不水
额请问你是初学者吗
novice一枚
那没事了