排序与比较器　例题与练习

// 例题 ①「成绩排名」—— 排序与比较器组
//
// 三件事一次学完：struct 打包、lambda 当比较规则、**并列时怎么办**。
// ⚠ 题面要求「分数相同按输入顺序」，而 sort 是**不稳定**的 ——
//    不能指望它自己保住输入顺序，得**把输入序号也写进比较规则里**。

#include <bits/stdc++.h>
using namespace std;

struct Student {                      // ⚠ 花括号后面这个分号不能漏
    string name;
    int score;
    int id;                           // 输入序号 —— 就是为了并列时能分出高下
};

int main() {
    int n;
    cin >> n;

    vector<Student> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].name >> a[i].score;
        a[i].id = i;
    }

    sort(a.begin(), a.end(), [](const Student &x, const Student &y) {
        // 返回的是「x 该排在 y 前面吗」，不是「谁更大」
        if (x.score != y.score) return x.score > y.score;   // 分数高的在前
        return x.id < y.id;                                 // 分数一样：先来的在前
        // ⚠ 绝对不能写成 return x.score >= y.score;
        //    相等时也说「x 排前面」，sort 会一直往前找、越过数组边界。
    });

    for (const Student &s : a) cout << s.name << ' ' << s.score << "\n";
    return 0;
}

// 例题 ②「按右端点排序」—— 排序与比较器组
//
// 第 19、20 章的区间贪心，第一步永远是「按右端点排序」。
// 这里不用写比较器：pair 自带的规矩就是「先比 first，first 一样再比 second」
// ⇒ 只要把要排的那个量放在 first 就行。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> a(n);      // 存成 (右端点, 左端点)
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        a[i] = {r, l};                // ⚠ 谁放 first 是**约定**不是类型 —— 放反了编译器一声不吭
    }

    sort(a.begin(), a.end());         // 按 r 升序，r 相同按 l 升序

    for (const auto &p : a) cout << p.second << ' ' << p.first << "\n";
    return 0;
}