企业官网建设流程全解析

【题目来源】

学而思编程：毕业照

【题目描述】

又到了一年毕业季，学校里到处都是拍毕业照的人，小猴已经和各种朋友拍了一上午，现在到了班级合影的时间了。

小猴班里一共有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_{t+1}\ge \dots \ge h_{n-1}\ge h_nh1​≤h2​≤⋯≤ht−1​≤ht​,ht+1​≥⋯≥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_{t+1},h_{t+2},\dots,h_nht+1​,ht+2​,…,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

【核心思想】

1. 问题分析：给定N NN个同学的身高，需要重排成"好看"的队伍：前一段为奇数且非降序，后一段为偶数且非升序。这是一个自定义排序问题，关键在于设计比较函数实现奇偶分组和各自方向的排序。

2. 算法选择：

   • 自定义比较函数：先按奇偶分组（奇数在前），同奇偶时按指定方向排序
   • 标准排序：sort配合自定义比较函数一次性完成重排

3. 关键步骤：

   • 初始化：读取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)
     • 输出排序后的数组

4. 时间/空间复杂度：

   • 时间复杂度：O ( N log ⁡ N ) O(N \log N)O(NlogN)，排序
   • 空间复杂度：O ( N ) O(N)O(N)，存储数组

5. 自定义排序的核心思想：

   • 多级排序键：第一关键字为奇偶性（奇数优先），第二关键字为数值方向（奇数升序、偶数降序）
   • 比较函数完备性：覆盖所有情况（奇-奇、偶-偶、奇-偶、偶-奇），确保全序关系
   • 严格弱序：cmp满足传递性和反对称性，符合sort要求
   • 单趟排序：无需先分组再分别排序，自定义比较函数一次性完成全局最优排列
   • 适用于"多条件分组排序"类问题，比较函数是实现复杂排序规则的关键

【算法标签】

#其他排序

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;inth[100010];// 存储数组// 自定义比较函数boolcmp(intx,inty){// 如果都是奇数，按升序排序if(x%2==1&&y%2==1){returnx<y;}// 如果都是偶数，按降序排序if(x%2==0&&y%2==0){returnx>y;}// 一奇一偶，奇数在前（因为奇数%2=1，偶数%2=0）returnx%2>y%2;// 1 > 0}intmain(){intn;cin>>n;// 输入数组长度for(inti=1;i<=n;i++){cin>>h[i];// 输入数组元素}// 使用自定义比较函数排序sort(h+1,h+n+1,cmp);// 输出排序结果for(inti=1;i<=n;i++){cout<<h[i]<<" ";}return0;}

【运行结果】

5 160 175 138 174 137 137 175 174 160 138