链接:https://ac.nowcoder.com/acm/contest/1001/B
来源:牛客网
题目描述
在一条数轴上有N家商店,它们的坐标分别为 A[1]~A[N]。现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
输入描述:
第一行一个整数N,第二行N个整数A[1]~A[N]。
输出描述:
一个整数,表示距离之和的最小值。
示例1
输入
4
6 2 9 1
输出
12
思路:
仔细分析不难发现,当货仓在两个商店之间时,无论在什么位置,到两个商店的距离和不变。所以只需将输入的数全排列,依次用最大的减去最小值之和即可得出答案。
#include<bits/stdc++.h> using namespace std; int main(){ int N,a[100010],sum=0; cin>>N; for(int i=1;i<=N;i++) cin>>a[i]; sort(a+1,a+N+1); for(int i=1;i<=N/2;i++) sum+=a[N+1-i]-a[i]; cout<<sum; }