题目链接:https://ac.nowcoder.com/acm/contest/1001/B
题意:在一条数轴上有
N
N
N 家商店,它们的坐标分别为
A
[
1
]
∼
A
[
N
]
A[1] \sim A[N]
A[1]∼A[N]。现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
思路:
把
A
[
1
]
∼
A
[
N
]
A[1] \sim A[N]
A[1]∼A[N] 排序,设货仓建在
X
X
X 坐标处,
X
X
X 的左侧有
P
P
P 家商店,右侧有
Q
Q
Q 家商店。
因此,货仓应该建在中位数处,即把
A
[
]
A[\ ]
A[ ] 排序后,当
N
N
N 为奇数时,货仓建在
A
[
(
N
+
1
)
/
2
]
A[(N +1)/2]
A[(N+1)/2] 处最优;当
N
N
N 为偶数时,货仓建在
A
[
N
/
2
]
∼
A
[
N
/
2
+
1
]
A[N/2] \sim A[N/2 + 1]
A[N/2]∼A[N/2+1] 之间的任何位置都是最优解。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
int res = 0;
for (int i = 1; i <= n; i++)
{
res += abs(a[i] - a[n + 1 >> 1]);
}
printf("%d\n", res);
return 0;
}