G4018 [GESP202506 四级] 排序 题解

知识点：双重枚举、多关键字比较、计数。

解题思路

按目标顺序“身高降序、同高体重降序”定义比较，统计原序列中满足i<j且(h_i,w_i)<(h_j,w_j)的下标对。

为什么正确

每个逆序对至少需一次相邻交换，冒泡式交换每次恰减少一个逆序对，因此逆序对数就是最少交换数。

易错点

两项完全相同不构成逆序；答案最多n(n-1)/2，用long long。

复杂度

时间O(n²)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<pair<long long,long long>>a(n);
    for(auto &p:a)cin>>p.first>>p.second;
    long long ans=0;
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)ans+=a[i]<a[j];
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。