G4026 [GESP202606 四级] 身高体重指数 题解

知识点：自定义排序、比例比较、定点数。

解题思路

把身高换算成整数厘米，比较w_ih_j²与w_jh_i²，按BMI从高到低排序编号。

为什么正确

身高均为正，交叉相乘保持两个体重除身高平方的大小，统一厘米的比例因子相互抵消。

易错点

题目保证BMI不相同；将浮点米乘100后四舍五入成整数，交叉乘积用long long。

复杂度

时间O(n log 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<long long>w(n),h(n);
    for(auto &x:w)cin>>x;
    for(auto &x:h) {
        double v;
        cin>>v;
        x=llround(v*100);
    }
    vector<int>p(n);
    iota(p.begin(),p.end(),0);
    sort(p.begin(),p.end(),[&](int i,int j){return w[i]*h[j]*h[j]>w[j]*h[i]*h[i];});
    for(int i:p)cout<<i+1<<" ";
}

说明

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