P4672 合影效果（基础）

解题思路

合影时男生女生要分开站：男生全部站左边，从矮到高排；女生全部站右边，从高到矮排。这就像体育课排队，老师先喊"男左女右"分成两大组，再分别按身高调整顺序。

程序里把每个人的性别和身高装进结构体，sort 排序的规则分两步：先比性别，男生（0）排在女生（1）前面；性别相同时再比身高，男生从矮到高，女生从高到矮。写比较函数时要注意：男生和女生的身高排序方向相反，所以要判断一下当前这个人是男是女，再决定按哪个方向排。

边界：题目保证至少有 1 个男生和 1 个女生，所有人的身高都不相同，所以不会出现两个人完全一样导致比较函数拿不定主意的情况。

参考代码

// P4672 合影效果：男生在左从矮到高，女生在右从高到矮
#include <iostream>
#include <algorithm>
using namespace std;

struct Person {
    int g; // 性别：0男生 1女生
    int h; // 身高
};

bool cmp(const Person &a, const Person &b) {
    if (a.g != b.g) return a.g < b.g; // 男生(0)全部排在左边
    if (a.g == 0) return a.h < b.h;   // 男生从矮到高
    return a.h > b.h;                  // 女生从高到矮
}

Person p[45];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i].g >> p[i].h;
    }
    sort(p, p + n, cmp);
    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << p[i].h;
    }
    cout << endl;
    return 0;
}

复杂度分析

sort 排序 n 个人，时间复杂度 O(n log n)，n ≤ 40，排序次数很少，非常快。空间复杂度 O(n)，用来存所有人的性别和身高。