攀爬者

题意

给出 n 个三维点，每个点的高度 z 互不相同。攀爬路线必须从低到高经过所有点，求相邻经过点之间的三维欧几里得距离之和。

思路

因为每一步都必须到一个更高的点，并且要经过所有点，所以路线没有选择余地：把所有点按 z 从小到大排序，就是唯一的经过顺序。

然后枚举排序后相邻的两点，累加：

\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}

最后保留三位小数输出。

Python 知识

把点存成 (z, x, y)，直接 points.sort() 就会按高度 z 升序排列。
math.sqrt(value) 计算平方根。
f"{distance:.3f}" 按三位小数格式化浮点数。
n 最大到 50000，使用 sys.stdin.buffer.read() 读入更稳妥。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24import math
import sys

data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]

points = []
index = 1
for _ in range(n):
    x = data[index]
    y = data[index + 1]
    z = data[index + 2]
    points.append((z, x, y))
    index += 3

points.sort()

distance = 0.0
for i in range(n - 1):
    z1, x1, y1 = points[i]
    z2, x2, y2 = points[i + 1]
    distance += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2 + (z1 - z2) ** 2)

print(f"{distance:.3f}")

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
37
38
39
40
41
42
43
44
45
46
47/**
 * 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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

struct Point {
    int x, y, z;
};

int n;
Point pts[MAXN];

// 按高度 z 升序排序
bool cmp(const Point &a, const Point &b) {
    return a.z < b.z;
}

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y >> pts[i].z;
    }

    sort(pts, pts + n, cmp);

    double ans = 0.0;
    for (int i = 0; i < n - 1; i++) {
        double dx = pts[i].x - pts[i + 1].x;
        double dy = pts[i].y - pts[i + 1].y;
        double dz = pts[i].z - pts[i + 1].z;
        ans += sqrt(dx * dx + dy * dy + dz * dz);
    }

    cout << fixed << setprecision(3) << ans << "\n";

    return 0;
}

复杂度

排序时间复杂度为 $O(n \log n)$ ，累加距离为 $O(n)$ ，总时间复杂度为 $O(n \log n)$ 。空间复杂度为 $O(n)$ 。

总结

题目看起来像路径问题，但高度严格递增并且必须经过所有点，直接把路线固定成按 z 排序。

目录

题意

思路

Python 知识

代码

复杂度

总结