8.22集训笔记

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
struct T{
    int x,y,z;
}a[N];

bool cmp(T a,T b){
    return a.z < b.z; // 返回是否合法，或者说 是否不需要交换 
}
double dis(int i,int j){
    return sqrt(
        pow(a[i].x - a[j].x, 2) + 
        pow(a[i].y - a[j].y, 2) + 
        pow(a[i].z - a[j].z, 2) ); 
}
int main(){
    int n,x,y,z; cin>>n;
    for(int i=1; i<=n; i++){
        cin>>x>>y>>z; a[i] = {x,y,z};// c++11
    }
    sort(a+1, a+1+n, cmp);
    double ans=0;
    for(int i=1; i<n; i++) ans += dis(i, i+1);    
    cout<<fixed<<setprecision(3)<<ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N];

bool cmp(int a,int b){
    return a < b;
}
// 冒泡：每次比较两个相邻的数 
int cnt=0; // 逆序对 
void bubble_sort(){
    for(int i=n; i>=1; i--)// 第 n-i+1 轮冒泡
        for(int j=1; j<i; j++) 
            if(a[j] > a[j+1]) {
                swap(a[j], a[j+1]);
                cnt++; // 每次冒泡，就是解决一个逆序对 
            }
}
// 选择：选择最大的放在最后 
void select_sort(){
    for(int i=n; i>=1; i--){
        int k = i; // 最大值的位置
        for(int j=1; j<i; j++) if(a[k]<a[j]) k=j;
        swap(a[k], a[i]); 
    }
}
// 插入：将当前元素插入到前面的有序序列中 
void insert_sort(){
    for(int i=2; i<=n; i++){
        int k = i; // 要插入的元素位置
        for(int j=i-1; j>=1; j--){
            if(a[k] >= a[j]) break;
            swap(a[k], a[j]), k=j;
        } 
    }
}
int main(){
    freopen("data.in", "r", stdin);
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);

//    sort(a+1, a+1+n); // 默认升序，less<int>()
//    sort(a+1, a+1+n, cmp);   // 自定义比较函数 cmp 
//    sort(a+1, a+1+n, less<int>());   // 升序 less<int>()
//    sort(a+1, a+1+n, greater<int>()); // 降序 greater<int>()
//    sort 本身内部封装 快速排序，堆排序，插入排序 
//  快速排序：O(nlogn) 选择一个基准值 b，将元素分为两部分，左边 <b, 右边 >=b 
//    bubble_sort();
//    select_sort();
    insert_sort();
    for(int i=1; i<=n; i++) printf("%d ", a[i]);
    return 0;
}