货仓选址
在一条数轴上有 N 家商店,它们的坐标分别为 A1~AN。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。
为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数N。
第二行N个整数A1~AN。
输出格式
输出一个整数,表示距离之和的最小值。
数据范围
1≤N≤100000,
0≤Ai≤40000
输入样例:
4
6 2 9 1
输出样例:
12
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long LL;
const int CNT = 100000;
/*
基于一个规律: A ----p---- B
p 位于 AB之间 时候,到二者距离恰二者间距离,此外均大于等于该值;
因此对当前轴上的所有商店考虑,
取 最左端和最右端 商店,位于二者之间则最小,并且到二者距离和不再变化;
取 次左端和次右端 商店,位于二者之间则最小,并且到二者距离和不再变化;
...
以此类推,题意要求获得 最靠中间的点。
思维提升点:
模型简化后,得到在中间距离和较小——随后考虑在中间距离小的原因,便得到如上规律
*/
// s for shop location;
int s[CNT + 5];
int main() {
int n;
cin >> n;
memset(s, 0, sizeof(s));
for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
}
// 排序以便计算距离;
sort(s + 1, s + n + 1);
LL ans = 0;
// 以 层次方式 选择最值作差,计算距离和;
for (int i = 1; i <= (n / 2); i++) {
ans += (s[n - i + 1] - s[i]);
}
cout << ans << endl;
return 0;
}