【题目来源】学而思编程毕业照【题目描述】又到了一年毕业季学校里到处都是拍毕业照的人小猴已经和各种朋友拍了一上午现在到了班级合影的时间了。小猴班里一共有N NN名同学现在站成一排其中从左往右数第i ii个人的身高为h i h_ihi​但是现在的队伍看着太难看了我们说一个在好看的队伍中每个人的身高满足h 1 ≤ h 2 ≤ ⋯ ≤ h t − 1 ≤ h t , h t 1 ≥ ⋯ ≥ h n − 1 ≥ h n h_1\le h_2\le \dots \le h_{t-1}\le h_t,h_{t1}\ge \dots \ge h_{n-1}\ge h_nh1​≤h2​≤⋯≤ht−1​≤ht​,ht1​≥⋯≥hn−1​≥hn​其中h 1 , h 2 , … , h t h_1,h_2,\dots,h_th1​,h2​,…,ht​均为奇数h t 1 , h t 2 , … , h n h_{t1},h_{t2},\dots,h_nht1​,ht2​,…,hn​均为偶数。现在小猴想要让拍照的队伍变得好看一些你能帮他算一算最后的队伍是什么样的么【输入】第一行一个正整数N NN表示同学的个数第二行N NN个正整数h 1 , h 2 , … , h N h_1,h_2,\dots,h_Nh1​,h2​,…,hN​表示每个同学的身高。【输出】一行用空格隔开的N NN个正整数表示整理后队伍的身高。【输入样例】5 160 175 138 174 137【输出样例】137 175 174 160 138【核心思想】问题分析给定N NN个同学的身高需要重排成好看的队伍前一段为奇数且非降序后一段为偶数且非升序。这是一个自定义排序问题关键在于设计比较函数实现奇偶分组和各自方向的排序。算法选择自定义比较函数先按奇偶分组奇数在前同奇偶时按指定方向排序标准排序sort配合自定义比较函数一次性完成重排关键步骤初始化读取N NN和身高数组h [ 1.. N ] h[1..N]h[1..N]自定义比较函数cmp(x, y)若x xx和y yy均为奇数返回x y奇数内部升序若x xx和y yy均为偶数返回x y偶数内部降序否则一奇一偶返回x % 2 y % 2奇数在前因为1 0排序并输出sort(h 1, h N 1, cmp)输出排序后的数组时间/空间复杂度时间复杂度O ( N log ⁡ N ) O(N \log N)O(NlogN)排序空间复杂度O ( N ) O(N)O(N)存储数组自定义排序的核心思想多级排序键第一关键字为奇偶性奇数优先第二关键字为数值方向奇数升序、偶数降序比较函数完备性覆盖所有情况奇-奇、偶-偶、奇-偶、偶-奇确保全序关系严格弱序cmp满足传递性和反对称性符合sort要求单趟排序无需先分组再分别排序自定义比较函数一次性完成全局最优排列适用于多条件分组排序类问题比较函数是实现复杂排序规则的关键【算法标签】#其他排序【代码详解】#includebits/stdc.husingnamespacestd;inth[100010];// 存储数组// 自定义比较函数boolcmp(intx,inty){// 如果都是奇数按升序排序if(x%21y%21){returnxy;}// 如果都是偶数按降序排序if(x%20y%20){returnxy;}// 一奇一偶奇数在前因为奇数%21偶数%20returnx%2y%2;// 1 0}intmain(){intn;cinn;// 输入数组长度for(inti1;in;i){cinh[i];// 输入数组元素}// 使用自定义比较函数排序sort(h1,hn1,cmp);// 输出排序结果for(inti1;in;i){couth[i] ;}return0;}【运行结果】5 160 175 138 174 137 137 175 174 160 138