1170 合影效果
大约 2 分钟
1170 合影效果
【算法】 排序
【C++】 sort、string、vector、cmp 比较函数
【难度】 入门
一、题目简述
小云和朋友们合影。站队规则:
- 男生全部在左(从拍照者角度),按从矮到高从左到右排
- 女生全部在右,按从高到矮从左到右排
所有人的身高都不同。给定 个人的性别和身高,输出合影效果。
二、解题思路
2.1 问题分解
本质上就是分类 + 分类内排序:
- 把所有人按性别分成两组:男生组、女生组
- 男生组:按身高升序排列
- 女生组:按身高降序排列
- 输出:先输出所有男生身高(空格分隔),再输出所有女生身高
2.2 实现方式
方法一:用两个数组分别存男生和女生身高,分别排序后输出。
方法二:所有人放一起,用 cmp 函数处理分类逻辑(略复杂,不推荐)。
推荐方法一,思路清晰,不易出错。
2.3 手动模拟
假设输入:
6
male 170
female 165
male 175
female 160
male 168
female 158分组:
- 男生身高:
[170, 175, 168]→ 升序排序 →[168, 170, 175] - 女生身高:
[165, 160, 158]→ 降序排序 →[165, 160, 158]
输出:168 170 175 165 160 158
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
double male[45], female[45]; // n 不太大
int m_cnt = 0, f_cnt = 0;
for (int i = 0; i < n; i++) {
string gender;
double height;
cin >> gender >> height;
if (gender == "male") {
male[m_cnt++] = height;
} else {
female[f_cnt++] = height;
}
}
// 男生:从矮到高(升序)
sort(male, male + m_cnt);
// 女生:从高到矮(降序)
sort(female, female + f_cnt, greater<double>());
// 或者 sort(female, female + f_cnt); reverse(female, female + f_cnt);
// 输出男生
for (int i = 0; i < m_cnt; i++) {
cout << male[i] << " ";
}
// 输出女生
for (int i = 0; i < f_cnt; i++) {
cout << female[i] << " ";
}
cout << endl;
return 0;
}
greater<double>()是 C++ 标准库提供的函数对象,等价于从大到小排序。也可以sort后reverse,效果相同。
四、复杂度分析
- 时间复杂度:,两次排序的总开销。实际效率取决于 的大小。
- 空间复杂度:,两个数组分别存储男生和女生身高。
五、知识扩展
5.1 sort 的三种用法
sort(a, a + n); // 默认升序
sort(a, a + n, greater<int>()); // 降序(使用函数对象)
sort(a, a + n, cmp); // 自定义比较函数5.2 浮点数输出格式
如果题目要求保留小数位数,可以用 printf:
printf("%.2f ", height);或用 cout 配合 fixed + setprecision:
cout << fixed << setprecision(2) << height << " ";