ACW104
题意
在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数N。
第二行N个整数A1~AN。
输出格式
输出一个整数，表示距离之和的最小值。
数据范围
1≤N≤100000
输入样例：
1
2
4
6 2 9 1
输出样例：
1
12
思路
这个题其实很简单,我们从两个方面解答一下
-
几何角度
我们画一条数轴,上面分布着N个点,我们不妨将仓库放在第一个点左侧,我们发现,即使都是第一个点左侧,也是越靠近第一个点,总距离越小.
我们把这个结论一般化.如果仓库左侧有p个商店,右侧有q个商店(此处假设仓库不与任何一个点重合),如果p>q,则仓库挪到其左边最近的商店一定是此区间的最优解.如果q>p,则挪到其右边最近的仓库显然更优.如果p==q,则区间内仓库在哪都一样.
综上所述,我们发现,仓库应该建立在商店坐标的中位数的位置,因为如果在中位数左侧,靠右会获得更优解,如果在中位数右侧,靠左会获得更优解.
-
数学角度 \(sum = \sum_{i=1}^n |a_i-pos|\) 如果让sum取得最小值,则pos的取值应当是a数列的中位数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 此题思路有了,编码就没有难度
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#include <unordered_map>
#define ll long long
#define LL ll
using namespace std;
int n;
int shop[100010];
int myAbs(int x) {
if (x >= 0) {
return x;
}
return -x;
}
int main() {
while (cin >> n) {
for (int i = 0; i < n; ++i) {
cin >> shop[i];
}
sort(shop, shop + n);
ll ans = 0;
for (int i = 0; i < n; ++i) {
ans += myAbs(shop[i] - shop[n / 2]);
}
cout << (ll) ans << endl;
}
return 0;
}
