P4638 香山合影（基础）

解题思路

这道题考察的是分组排序。同学们去香山玩，要站成一排合影。规则是：男生全部站在左边，并且从矮到高排；女生全部站在右边，并且从高到矮排。所有人的身高都不同。我们只要把每个人的性别和身高读进来，按规则排好队，再把身高从左到右输出就行。

思路很直接：把男生和女生先分开，存到两个不同的数组里。然后分别排序——男生从矮到高（升序），女生从高到矮（降序）。最后先输出全部男生的身高，再输出全部女生的身高，中间用空格隔开，就是拍照者眼中从左到右的顺序。

怎么区分男女呢？输入里性别是字符串 male 或 female。我们不需要完整比较整个字符串，只要看第一个字符：m 开头的就是男生，f 开头的就是女生。

排序方法：n 最大只有 40，人数很少，用简单的冒泡排序就足够了。冒泡排序的思想是：从头到尾两两比较相邻的两个数，如果顺序不对就交换，这样每趟下来最大的（或最小的）数就会"冒泡"到它该在的位置，重复若干趟后整个数组就有序了。男生组按照"前一个比后一个高就交换"来排，最后得到从矮到高的顺序；女生组反过来，按照"前一个比后一个矮就交换"来排，得到从高到矮的顺序。

输出时有两个细节要注意。第一，身高是浮点数，要求保留两位小数，比如 1.72 米。可以自己写一个输出函数，把身高乘以 100 四舍五入后拆成整数部分和小数部分，再补零输出；第二，相邻两个身高之间要用一个空格隔开，但第一个身高前面不能有空格，最后一个身高输出后要换行。

边界情况：题目保证至少有 1 个男生和 1 个女生，且 n 在 2 到 40 之间，所以两个数组都一定非空，不会出现"有一边没人"的情况。

参考代码

// 把男生按从矮到高、女生按从高到矮排列后输出。
#include <iostream>
using namespace std;

// 输出保留两位小数的身高。
void out2(double x) {
    long long v = (long long)(x * 100 + 0.5); // 把身高放大100倍并四舍五入。
    int d = (int)(v % 100); // 取出小数部分。
    cout << v / 100 << '.'; // 输出整数部分和小数点。
    if (d < 10) cout << 0; // 一位小数时补零。
    cout << d; // 输出两位小数。
}

int main() {
    int n; // 总人数。
    double male[45]; // 保存男生身高。
    double female[45]; // 保存女生身高。
    int mc = 0; // 男生人数。
    int fc = 0; // 女生人数。
    int i; // 循环变量。
    cin >> n; // 读入总人数。
    for (i = 0; i < n; i++) { // 读入每个人的信息。
        char sex[10]; // 性别字符串。
        double h; // 当前人的身高。
        cin >> sex >> h; // 读入性别和身高。
        if (sex[0] == 'm') { // male开头是男生。
            male[mc] = h; // 保存男生身高。
            mc++; // 男生人数加一。
        } else { // 否则是女生。
            female[fc] = h; // 保存女生身高。
            fc++; // 女生人数加一。
        }
    }
    for (i = 0; i < mc - 1; i++) { // 排序男生身高。
        int j; // 内层循环变量。
        for (j = 0; j < mc - 1 - i; j++) { // 比较相邻男生。
            if (male[j] > male[j + 1]) { // 男生应从矮到高。
                double t = male[j]; // 暂存一个男生身高。
                male[j] = male[j + 1]; // 较矮者向前。
                male[j + 1] = t; // 较高者向后。
            }
        }
    }
    for (i = 0; i < fc - 1; i++) { // 排序女生身高。
        int j; // 内层循环变量。
        for (j = 0; j < fc - 1 - i; j++) { // 比较相邻女生。
            if (female[j] < female[j + 1]) { // 女生应从高到矮。
                double t = female[j]; // 暂存一个女生身高。
                female[j] = female[j + 1]; // 较高者向前。
                female[j + 1] = t; // 较矮者向后。
            }
        }
    }
    for (i = 0; i < mc; i++) { // 输出男生队伍。
        if (i > 0) cout << ' '; // 身高之间用空格隔开。
        out2(male[i]); // 输出男生身高。
    }
    for (i = 0; i < fc; i++) { // 输出女生队伍。
        cout << ' '; // 男生和女生之间也用空格隔开。
        out2(female[i]); // 输出女生身高。
    }
    cout << '\n'; // 输出换行。
    return 0; // 程序正常结束。
}

复杂度分析

时间上，男生和女生两组分别做冒泡排序，最坏情况下每组的排序时间与人数平方成正比，所以总时间复杂度是 O(n²)。但 n 最大只有 40，40²=1600 次操作，非常快。如果数据量再大，可以换成 O(n log n) 的快速排序。空间上，用两个大小固定的数组保存男生和女生身高，空间复杂度是 O(n)。