题目描述
在一条数轴上有 N 家商店,它们的坐标分别为 A1~AN。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。
为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数N。
第二行N个整数A1~AN。
输出格式
输出一个整数,表示距离之和的最小值。
数据范围
1≤N≤100000,
0≤Ai≤40000
样例
// input
4
6 2 9 1
// output
12
算法1
(线性时间查找) $O(n)$
直接线性时间查找。
时间复杂度
O(n)
实际耗时:37ms
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
int N, A[100000], w;
long long sum = 0, temp=0;
inline void readUnsigned(int& x)
{
x = 0;
char s = getchar();
while (s < '0' || s>'9')
s = getchar();
while (s >= '0' && s <= '9') {
x = x * 10 + s - '0';
s = getchar();
}
}
void input() {
readUnsigned(N);
int i = 0;
while (i < N) {
readUnsigned(A[i++]);
}
}
int partition(int p, int r, int x)
{
int i = p - 1, j = r + 1;
while (true)
{
while (A[++i] < x && i < r);
while (A[--j] > x);
if (i >= j)
{
break;
}
std::swap(A[i], A[j]);
}
return j;
}
int select(int p, int r, int k)
{
if (r - p < 75)
{
std::sort(A+p, A+r);
return A[p + k - 1];
}
for (int i = 0; i <= (r - p - 4) / 5; i++)
{
std::sort(A+(p + 5 * i), A+(p + 5 * i + 4));
std::swap(A[p + 5 * i + 2], A[p + i]);
}
int x = select(p, p + (r - p - 4) / 5, (r - p - 4) / 10);
int i = partition(p, r, x);
int j = i - p + 1;
if (k <= j)
{
return select(p, i, k);
}
else
{
return select(i + 1, r, k - j);
}
}
void compute() {
int i = 0;
w=select(0,N-1,N%2==0?N/2:N/2+1);
while (i < N) {
sum += ((A[i] > w) ? (A[i++] - w) : (w - A[i++]));
}
}
int main()
{
input();
compute();
std::cout << sum;
return 0;
}