快排最后三个还能TLE吗,还有这事
  • 板块P5143 攀爬者
  • 楼主Vera_suki
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/7/14 11:21
  • 上次更新2023/11/3 09:57:06
查看原帖
快排最后三个还能TLE吗,还有这事
916946
Vera_suki楼主2023/7/14 11:21
#include <bits/stdc++.h>
#define int long long


using namespace std;

typedef struct{
    double x;
    double y;
    double z;
}fix;

vector<fix> q;
double S=0;
int n;

void quick_sort(vector<fix> &q,int l,int r){
    if (l>=r) return ;

    int i=l-1,j=r+1,x=q[l].z;

    while (i<j){
        do i++; while (q[i].z<x);
        do j--; while (q[j].z>x);
        if (i<j) swap(q[i],q[j]);
    }

    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

signed main(){

    cin>>n;

    for (int i=0;i<n;i++){
        fix tmp;
        cin>>tmp.x>>tmp.y>>tmp.z;

        q.push_back(tmp);
    }

    for (int i=0;i<n;i++)
        for (int j=0;j<n-i-1;j++)
            if (q[j].z>q[j+1].z) swap(q[j],q[j+1]);

    quick_sort(q,0,n-1);

    for (int i=0;i<n-1;i++)
        S+= sqrt(pow(q[i].x-q[i+1].x,2)+pow(q[i].y-q[i+1].y,2)+pow(q[i].z-q[i+1].z,2));

    printf("%.3lf",S);

    return 0;
}
2023/7/14 11:21
加载中...