当前位置：首页 > article >正文

《攀爬者》

article 2025/1/7 12:20:21

题目背景

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

题目描述

他在地形图上标记了 NN 个点，每个点 PiPi 都有一个坐标 (xi,yi,zi)(xi,yi,zi)。所有点对中，高度值 zz 不会相等。HKE 准备从最低的点爬到最高的点，他的攀爬满足以下条件：

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

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

(3) HKE 会飞，他从一个点 PiPi 爬到 PjPj 的距离为两个点的欧几里得距离。即，(Xi−Xj)2+(Yi−Yj)2+(Zi−Zj)2(Xi−Xj)2+(Yi−Yj)2+(Zi−Zj)2

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

输入格式

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

接下来 NN 行，三个整数 xi,yi,zixi,yi,zi 表示第 ii 个点的坐标。

输出格式

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

输入输出样例

输入 #1复制

输出 #1复制

6.928

说明/提示

对于100%的数据，1≤N≤500001≤N≤50000，答案的范围在 double 范围内。

C语言代码实现：

EXAMPLE（1）（优化运行时间后）

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 比较函数，用于 qsort 对二维数组按照第三列元素排序
int compare(const void *a, const void *b) {
int *aa = (int *)a;
int *bb = (int *)b;
return aa[2] - bb[2];
}

int main(int argc, char *argv[]) {
int a[1000][3];
int n, i;
double sum = 0, q;

scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
}
// 使用 qsort 对数组进行排序
qsort(a, n, sizeof(int[3]), compare);

for (i = 0; i < n - 1; i++) {
q = sqrt(pow(a[i][0] - a[i + 1][0], 2) + pow(a[i][1] - a[i + 1][1], 2) + pow(a[i][2] - a[i + 1][2], 2));
sum += q;
}
printf("%.3f", sum);
return 0;
}

EXAMPLE（优化运行时间前）

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[])
{
    int a[1000][3],b1,b2,b3,n,i,j,k;
   double sum=0,q;
   scanf("%d",&n);
   for(i=0;i<n;i++)
   {
      scanf("%d %d %d",&a[i][0],&a[i][1],&a[i][2]);

   }
   for(i=0;i<n;i++)
   {
       for(j=0;j<n-i-1;j++)
       {
           if(a[j][2]>a[j+1][2])
           {
           b1=a[j][0];
           b2=a[j][1];
           b3=a[j][2];
           a[j][0]=a[j+1][0];
           a[j][1]=a[j+1][1];
           a[j][2]=a[j+1][2];
           a[j+1][0]=b1;
           a[j+1][1]=b2;
           a[j+1][2]=b3;

           }
       }
   }
   for(i=0;i<n-1;i++)
   {
       b1=a[i][0]-a[i+1][0];
       b1*=b1;
       b2=a[i][1]-a[i+1][1];
       b2*=b2;
       b3=a[i][2]-a[i+1][2];
       b3*=b3;
       q=b1+b2+b3;
       q=sqrt(q);
       sum+=q;
   }
   printf("%.3f",sum);
   return 0;
}