AcWing 104. 货仓选址
宋标 Lv5
  2022-08-18 02:31:36 2022-08-18 02:31    

题目

在一条数轴上有 家商店，它们的坐标分别为 。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数 。

第二行 个整数 。

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

,

输入样例：

4
6 2 9 1

输出样例：

12

题解

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100005;

int a[N];
int n;

void q_sort(int l, int r)
{
    if (l >= r) return;
    // x取第一位
    int i = l - 1, j = r + 1, x = l;
    while (i < j)
    {
        while (a[++ i] < a[x]);
        while (a[-- j] > a[x]);
        if (i < j) swap(a[i], a[j]);
    }
    // 取i会有边界值问题
    q_sort(l, j);
    q_sort(j + 1, r);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> a[i];
    q_sort(0, n - 1);
    int res = 0;
    // 取中间值则是最短距离
    for (int i = 0; i < n; ++ i) res += abs(a[i] - a[n / 2]);
    cout << res << endl;
    return 0;
}
 评论