描述

在一条数轴上有N家商店,它们的坐标分别为 A[1]~A[N]。现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。

输入格式

第一行一个整数N,第二行N个整数A[1]~A[N]。

输出格式

一个整数,表示距离之和的最小值。

样例输入

4
6 2 9 1

样例输出

12

数据范围与约定
对于100%的数据: N<=100000, A[i]<=1000000

解题思路:
显然建在中位数最优?有兴趣自己证明一下啥的?

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
int main(){
    int n=read();for(int i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+n+1);int mid,ret=0;
    if(n%2==1)mid=(n+1)/2;
    else mid=n>>1;
    for(int i=1;i<=n;i++)ret+=abs(a[i]-a[mid]);
    write(ret);
    return 0;
}

发表评论