P5143 攀爬者（快速排序）

题目背景

HKE 考完 GDOI 之后跟他的神犇小伙伴们一起去爬山。

题目描述

他在地形图上标记了 $N$ 个点，每个点 $P_i$ 都有一个坐标 $(x_i,y_i,z_i)$。所有点对中，高度值 $z$ 不会相等。HKE 准备从最低的点爬到最高的点，他的攀爬满足以下条件：

(1) 经过他标记的每一个点；

(2) 从第二个点开始，他经过的每一个点高度 $z$ 都比上一个点高；

(3) HKE 会飞，他从一个点 $P_i$ 爬到 $P_j$ 的距离为两个点的欧几里得距离。即，$\sqrt{(X_i-X_j{)}^2+(Y_i-Y_j{)}^2+(Z_i-Z_j{)}^2}$

现在，HKE 希望你能求出他攀爬的总距离。

输入格式

第一行，一个整数 $N$ 表示地图上的点数。

接下来 $N$ 行，三个整数 $x_i,y_i,z_i$ 表示第 $i$ 个点的坐标。

输出格式

一个实数，表示 HKE 需要攀爬的总距离（保留三位小数）

样例 #1

样例输入 #1

5
2 2 2
1 1 1
4 4 4
3 3 3
5 5 5
1
2
3
4
5
6

样例输出 #1

6.928
1

提示

对于100%的数据，$1\le N\le 50000$，答案的范围在 double 范围内。

1.题目分析

键入经过的所有点的坐标，
将所有点按照高度进行排序，
然后计算两两相邻坐标之间的欧几里得距离之和。

值得一提的是，这道题不能采用简单的冒泡排序或者选择排序，因为会导致时间复杂度过高。所以必须采用快速排序才行。

c++内置的sort排序底层就是快速排序：
需要引用头文件：

#include 
1

这里说几点传参问题：
例如：sort(pos,pos+n,cmp);

• 第一个参数代表数组的起始地址的指针
• 第二个参数代表数组的结束地址的指针
• 第三个参数重写排序规则的函数

2.题目思路

1. 定义一个结构体存储各个点的坐标
2. 定义sort排序规则:按照高度从低到高进行排序
3. 进入主函数
4. 将各个点的信息存入结构体数组
5. 调用sort排序，对点的高度进行升序排序
6. 计算总距离：相邻两个点求欧几里得距离之和
7. 打印保留三位小数

3.代码实现

#include 
#include 
#include 

using namespace std;
//结构体记录每一个坐标
typedef struct data {
    double x, y, z;
} point;

//定义排序规则
//按照高度从低到高进行排序
bool cmp(point x1, point y1) {
    return x1.z < y1.z;
}

int main() {
    int n;
    cin >> n;
    //总共需要经历的点
    point pos[n];
    for (int i = 0; i < n; ++i) {
        cin >> pos[i].x >> pos[i].y >> pos[i].z;
    }
    //这里采用快速排序
    //注意第三个参数使用的是使用函数指针，指定比较规则。
    sort(pos,pos+n,cmp);
    //计算总距离
    double sum = 0;
    //相邻两个点求欧几里得距离
    for (int i = 0; i < n - 1; ++i) {
        sum += sqrt(pow((pos[i].x - pos[i + 1].x), 2) + pow((pos[i].y - pos[i + 1].y), 2) +
                    pow((pos[i].z - pos[i + 1].z), 2));
    }
    //打印保留三位小数
    printf("%.3lf", sum);

    return 0;
}
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