洛谷 P5143 攀爬者 - 详细解题思路-洪萨配资

题目

蒟蒻的解题步骤

第一步：理解核心需求

这本质上是一个排序问题。既然要按照高度爬，那就必须先把所有点按z坐标排序。但有个细节要注意——如果两个点高度一样咋办？题目没说，我就自己定了规则：z相同看y，y相同再看x，确保顺序唯一

第二步：数据结构设计
我选择用结构体来存点，这样代码更清晰

struct AAA { int x, y, z; }a[50000];

~~不要去在意奇怪的命名，纯粹懒得起名了~~

第三步：解决排序问题
我写了一个比较函数，这是整个代码的核心

bool cmp(AAA a, AAA b) { if (a.z == b.z) // 先比高度 { if (a.y == b.y) // 高度一样比y { return a.x < b.x; // 还一样就比x } return a.y < b.y; } return a.z < b.z; }

第四步：计算距离
排序之后，计算距离就简单了，我直接从第二个点开始，每个点都和前面那个点算距离

for (int i = 1; i < p; i++) { X = a[i].x - a[i - 1].x; Y = a[i].y - a[i - 1].y; Z = a[i].z - a[i - 1].z; sum += sqrt((X * X) + (Y * Y) + (Z * Z)); }

这里我用的是最直接的三维距离公式，sqrt是标准库函数，不用自己实现

第五步：处理输出精度
题目要求保留三位小数

cout << fixed << setprecision(3) << sum;

fixed保证不用科学计数法，setprecision(3)设三位小数

我遇到的坑和解决方案

坑1：浮点数精度问题
一开始我担心整数平方会有溢出的可能，后来一想坐标值不会太大，int类型应该够用，而且我用的是double存中间结果，精度应该没问题。

坑2：边界情况
如果只有一个点咋办？我看了下循环是从i=1开始的，当p=1时循环不执行，sum保持0，正好符合要求。

坑3：排序规则是否必要
想了半天要不要写这么复杂的比较函数，为了确保结果，还是写了完整的三级比较。

我对代码的自我评价

这个代码我觉得有几个优点：

逻辑清晰：排序→计算→输出，步骤分明
效率不错：O(n log n)的排序加上O(n)的计算，50000个点完全能处理
可读性好：虽然结构体名字随便了点，但整体结构清晰

如果要说可以改进的地方：

结构体名字可以起得更有意义些
可以用引用传参避免拷贝

写代码时的小技↗巧↘

用bits/stdc++.h：比赛时省时间，不用记那么多头文件
变量名简单：X,Y,Z虽然简单，但在这里很直观
直接写计算式：不单独封装函数，减少调用开销

心得感受

其实这道题不算难，主要考察基本功。我写的时候最深的感受是：理解题意比写代码更重要。

我见过有人没注意要按高度排序，直接按输入顺序算距离，那肯定就错了。也有人在比较函数里写反了小于号，导致排序顺序不对。

对我来说，写这种题就像搭积木——先把问题分解成几个步骤（输入、排序、计算、输出），然后每个步骤用合适的代码实现，最后组合起来。

有时候我会想，如果我是出题人，我会怎么设计测试数据？可能我会放一些z相同的点，看选手有没有考虑到；也可能放一些坐标值很大的点，看会不会溢出

~~感受找ai概括的，真的不会总结啊喂~~

最后贴个全代码

#include<bits/stdc++.h> using namespace std; struct AAA { int x, y, z; }a[50000]; bool cmp(AAA a, AAA b) { if (a.z == b.z) { if (a.y == b.y) { return a.x < b.x; }return a.y < b.y; }return a.z < b.z; } int main() { int p; double X,Y,Z, sum=0; cin >> p; for (int i = 0; i < p; i++) { cin >> a[i].x >> a[i].y >> a[i].z; } sort(a, a + p,cmp); for (int i = 1; i < p; i++) { X=a[i].x - a[i - 1].x; Y=a[i].y - a[i - 1].y; Z=a[i].z - a[i - 1].z; sum+=sqrt((X * X) + (Y * Y) + (Z * Z)); } cout <<fixed<<setprecision(3)<< sum; return 0; }