【题目来源】洛谷B4558 [GESP202606 四级] 身高体重指数 - 洛谷【题目描述】一个人的身高体重指数BMI等于其体重千克为单位除以其身高米为单位的平方。例如一个体重为50 kg 50\text{ kg}50kg身高为1.6 m 1.6\text{ m}1.6m的人的身高体重指数为50 kg / 1.6 m / 1.6 m 19.53125 kg/m 2 50\text{ kg}/1.6\text{ m}/1.6\text{ m} 19.53125\text{ kg/m}^250kg/1.6m/1.6m19.53125kg/m2。现在有n nn个小朋友第i ii个小朋友的编号为i ii体重为w i w_iwi​身高为h i h_ihi​。请按照身高体重指数从高到低为小朋友们排序数据保证不存在两个小朋友的身高体重指数完全相同。输出排序后小朋友的编号。【输入】输入3 33行第一行为一个正整数n nn表示小朋友的个数第二行为n nn个整数w 1 , w 2 , ⋯ , w n w_1, w_2, \cdots, w_nw1​,w2​,⋯,wn​表示小朋友们的体重单位为kg \text{kg}kg第三行为n nn个浮点数h 1 , h 2 , ⋯ , h n h_1, h_2, \cdots, h_nh1​,h2​,⋯,hn​表示小朋友们的身高单位为m \text{m}m。【输出】输出一行n nn个数表示按照身高体重指数从高到低排序后的编号。【输入样例】3 45 33 39 1.55 1.33 1.44【输出样例】3 1 2【核心思想】问题分析给定n nn个小朋友的体重w i w_iwi​千克和身高h i h_ihi​米计算每个小朋友的 BMIB M I w i / h i 2 BMI w_i / h_i^2BMIwi​/hi2​然后按 BMI 从高到低排序并输出对应的编号。这是一个自定义排序问题核心在于正确计算 BMI 并维护编号与计算结果的映射关系。算法选择结构体封装使用结构体存储每个小朋友的 BMI 值和原始编号保持数据关联性自定义比较器定义按 BMI 降序的比较函数配合排序算法完成排序关键步骤读入数据读取n nn以及数组w [ 1.. n ] w[1..n]w[1..n]和h [ 1.. n ] h[1..n]h[1..n]计算 BMI遍历i ii从1 11到n nnp [ i ] . b ← 1.0 × w [ i ] / ( h [ i ] × h [ i ] ) p[i].b \leftarrow 1.0 \times w[i] / (h[i] \times h[i])p[i].b←1.0×w[i]/(h[i]×h[i])p [ i ] . i d x ← i p[i].idx \leftarrow ip[i].idx←i自定义排序定义比较函数c m p ( x , y ) cmp(x, y)cmp(x,y)返回x . b y . b x.b y.bx.by.b调用s o r t sortsort对p [ 1.. n ] p[1..n]p[1..n]排序输出结果按排序后的顺序输出p [ i ] . i d x p[i].idxp[i].idx时间/空间复杂度时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)计算 BMI 为O ( n ) O(n)O(n)排序为O ( n log ⁡ n ) O(n \log n)O(nlogn)空间复杂度O ( n ) O(n)O(n)存储n nn个结构体元素自定义排序的核心思想数据与索引绑定通过结构体将计算值BMI与原始编号封装在一起排序后仍能追溯原始身份避免排序后丢失对应关系浮点精度处理使用1.0 * w[i]将整数除法转为浮点除法确保 BMI 计算精度利用题目保证的不存在两个 BMI 完全相同避免浮点数比较精度问题比较器设计返回x . b y . b x.b y.bx.by.b实现降序排列若需升序则改为x . b y . b x.b y.bx.by.b稳定排序非必需由于题目保证 BMI 互不相同无需考虑相等元素的相对顺序直接使用快速排序即可适用于需要按计算指标排序并保留原始标识信息的基础排序类问题【算法标签】#普及- #语法基础【代码详解】#includebits/stdc.husingnamespacestd;constintN1005;// 常量最大小朋友数量intn;// n: 小朋友个数intw[N];// w[i]: 第 i 个小朋友的体重千克doubleh[N];// h[i]: 第 i 个小朋友的身高米structPerson// 小朋友结构体用于存储 BMI 和编号{doubleb;// b: 身高体重指数BMIintidx;// idx: 小朋友的编号}p[N];// p[i]: 第 i 个小朋友的信息boolcmp(Person x,Person y)// 比较函数按 BMI 从高到低排序{returnx.by.b;// BMI 大的排在前面}intmain(){cinn;// 读入小朋友个数for(inti1;in;i)// 读入 n 个小朋友的体重cinw[i];for(inti1;in;i)// 读入 n 个小朋友的身高cinh[i];for(inti1;in;i)// 计算每个小朋友的 BMI 并记录编号{p[i].b1.0*w[i]/(h[i]*h[i]);// BMI 体重 / 身高²p[i].idxi;// 记录小朋友编号}sort(p1,pn1,cmp);// 按 BMI 从高到低排序for(inti1;in;i)// 输出排序后的编号coutp[i].idx ;coutendl;return0;}【运行结果】3 45 33 39 1.55 1.33 1.44 3 1 2