P4673 教师节合唱（基础）

解题思路

这题和"合影效果"几乎一模一样，只是把"男生女生"换成了"学生老师"。学生全部站在左边，从矮到高排；老师站在学生的右边，从高到矮排。

排序规则：先按身份分，学生（0）在前，老师（1）在后；学生内部身高从小到大，老师内部身高从大到小。写比较函数时，身份不同就按身份分；身份相同再看身高，而且学生和老师的身高方向不一样，要分开写。

用 sort 加上这个比较函数，排完一次顺序就对了。最后按顺序输出每个人的身高，相邻两个数用空格隔开。边界：题目保证至少有 1 个学生和 1 个老师，身高都不相同。

参考代码

// P4673 教师节合唱：学生在左从矮到高，老师在右从高到矮
#include <iostream>
#include <algorithm>
using namespace std;

struct Person {
    int role; // 身份：0学生 1老师
    int h;    // 身高
};

bool cmp(const Person &a, const Person &b) {
    if (a.role != b.role) return a.role < b.role; // 学生(0)全部排在左边
    if (a.role == 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].role >> 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)，存所有学生和老师的信息。