【正经题解】排序

没死，冒个泡（

题目大意

现在给你 $n$ 名同学，你需要按照身高从高到低，相同则体重从重到轻的顺序排序，每次只能交换两名同学的位置。要求输出最少交换次数。

显然可以发现是冒泡排序。直接秒了

#include <bits/stdc++.h>
using namespace std;
struct node{
    int h,w;
}a[10005];
int main(){
    int n,ans=0;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i].h >>a[i].w;
    }for(int i=1;i<=n;i++){//冒泡排序，你知道的
        bool p=false;
        for(int j=1;j<=n-i;j++){
            if(a[j].h<a[j+1].h or a[j].h==a[j+1].h and a[j].w<a[j+1].w){
                p=true;
                swap(a[j],a[j+1]);
                ans++;
            }
        }if(p==false)break;
    }cout << ans;
    return 0;
}

时间复杂度： $O(n^2)$
空间复杂度 $O(n)$