货仓选址

题目描述

数轴上有 $N$ 家商店，坐标为 $A_1, A_2, \ldots, A_N$ 。在数轴上选一家货仓，使货仓到所有商店的距离之和最小，输出这个最小值。

输入：第一行整数 $N$ ，第二行 $N$ 个整数坐标。
输出：一个整数，表示最小距离和。
数据范围： $1 \le N \le 100\,000$ 。

样例输入 4 / 6 2 9 1，输出 12。

思路

$d(x)=\sum|x-A_i|$ 是下凸函数，最小值在中位数处取到。把坐标排序后让最小与最大配对，每组贡献 $B_{N+1-i}-B_i$ ，共 $\lfloor N/2\rfloor$ 组，求和即可。时间复杂度 $O(N\log N)$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 10:13
# update_at: 2026-10-01 10:17

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    coords: list[int] = sorted(next(data) for _ in range(n))  # 题面第二行的 N 个商店坐标

    # 排序后把最小与最大配成一组：|x-B_i|+|x-B_{N+1-i}| >= B_{N+1-i}-B_i（三角不等式）。
    # 取 x 为中位数时它同时落在每一组的区间内，所有组同时取等，于是差的和就是最小值；
    # N 为奇数时正中间那个元素与自身配对，差恒为 0，不必特判。
    pairs: int = n // 2  # 能配成 (小, 大) 的组数

    print(sum(coords[n - 1 - i] - coords[i] for i in range(pairs)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:13
 * update_at: 2026-10-06 11:13
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

ll a[MAXN]; // 商店坐标

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    sort(a + 1, a + n + 1); // 排序后两端配对

    ll ans = 0;
    int pairs = n / 2; // 组数 floor(N/2)，奇数时中间元素自配对差为0
    for (int i = 1; i <= pairs; ++i) {
        ans += a[n + 1 - i] - a[i]; // 第i组：大减小
    }

    cout << ans << '\n';
    return 0;
}

目录

题目描述

思路

参考代码