身高排排站#题解 - 帖子

题解：#G. 身高排排站

题目分析

这道题要求我们给一群人按身高排序。规则很简单：

主要规则：身高从低到高（升序）排。
次要规则：如果两个人身高一样，那么他们在输入时的先后顺序不能变。

🧠 最容易掉的“陷阱”

看到排序，我们第一反应可能是：

把每个人的身高和名字存起来。
直接调用 C++ 的 sort 函数，只按身高排序。

为什么这是错的？ 我们来看样例：

Alice 170
Bob 165
Cindy 170
Dave 180

Alice (170) 是在 Cindy (170) 之前输入的。
所以，按规则 2，在最终排好序的队伍里，Alice 也必须在 Cindy 之前。

正确的输出是：

Bob
Alice  <-- 170
Cindy  <-- 170
Dave

Alice 确实在 Cindy 前面。

那如果我们只按身高排序，会发生什么？ C++ 里的 std::sort 函数（它背后是快速排序算法）是一种不稳定排序 (Unstable Sort)。

术语解释：什么是“稳定排序”？

稳定排序 (Stable Sort)：想象你有两张牌，一张红桃 7，一张黑桃 7。它们的值都是 7。如果红桃 7 在黑桃 7 前面，一个“稳定”的排序算法在排序后，保证红桃 7 依然在黑桃 7 前面。
不稳定排序 (Unstable Sort)：一个“不稳定”的算法（比如快速排序）在处理这两个 7 时，它不保证它俩的原始顺序。它可能为了速度，把黑桃 7 换到红桃 7 前面去。

对应这道题：

Alice (170) 和 Cindy (170) 就像那两张 7。
std::sort 是“不稳定”的。当我们告诉它 "只按身高排" 时，它看到两个 170，它可能觉得 Alice 和 Cindy 没区别，就有可能会把 Cindy 换到 Alice 前面去，导致输出 Cindy, Alice。
这就违反了题目的“次要规则 2”。

💡 解决“不稳定”问题的方法

我们有两种方法来解决这个问题：

方法一：使用“稳定排序”算法 C++ 提供了另一个排序函数 std::stable_sort。它通常比 std::sort 慢一点，但它保证是稳定的。如果你只按身高用 stable_sort 排序，它在处理 Alice 和 Cindy 时，会发现她们身高相同，于是保证她们的原始顺序不变。
方法二：给“不稳定排序”一个更聪明的规则 (推荐) 这是竞赛中最常用的方法。我们不换算法，我们修改排序规则。

我们告诉 std::sort：
- “你先比较两个人的身高。”
- “如果身高不一样，你就按身高（从低到高）排。”
- “但如果身高一样，你就不要看身高了！请你去看他们的原始输入顺序，谁是先被输入的，谁就排在前面。”

💻 代码实现 (方法二)

为了实现这个“聪明的规则”，我们必须在读入数据时，就额外记录下每个人的“原始输入顺序”。

1. 如何存储“原始输入顺序”？

我们使用 struct (结构体) 来打包每个人的所有信息。struct 就像一个自定义的“盒子”，可以把不同类型的东西（名字、身高...）装在一起。

C++

struct Person {
    string name;  // 存名字
    int height;   // 存身高
    int index;    // 👈 关键！用来存这个人是第几个被输入的
};

2. 如何记录？

我们用一个 for 循环来读数据，循环变量 i（从 0 开始）天然就是“原始输入顺序”！

C++

vector<Person> people(n); // 创建一个能装 n 个“Person盒子”的数组
for (int i = 0; i < n; ++i) {
    cin >> people[i].name >> people[i].height;
    people[i].index = i; // 把当前的 i 存入盒子里
}
// 循环结束后，我们就有了：
// people[0] = { "Alice", 170, 0 }
// people[1] = { "Bob",   165, 1 }
// people[2] = { "Cindy", 170, 2 }
// people[3] = { "Dave",  180, 3 }

3. 如何编写“聪明的规则” (自定义比较器)？

我们把这个规则写在 sort 函数的第三个参数位置。这个规则（在 C++11 后通常用 Lambda 表达式 [](...){...} 来写）告诉 sort 如何比较两个人 a 和 b：

C++

// sort 内部会不断地挑两个 Person (a 和 b) 来问这个规则
sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    // 规则 1：先比较身高
    if (a.height != b.height) {
        // 如果身高不同，按身高升序排
        // (返回 true 表示 a 应该在 b 前面)
        return a.height < b.height; 
    } else {
        // 规则 2：如果身高相同，就比较原始顺序
        // (index 越小，说明输入越早，就越靠前)
        return a.index < b.index;
    }
});

当 sort 比较 Alice(170, 0) 和 Bob(165, 1)：
- a.height != b.height (170 != 165)
- 执行 return a.height < b.height; (170 < 165)，返回 false。
- sort 知道 a (Alice) 应该在 b (Bob) 后面。
当 sort 比较 Alice(170, 0) 和 Cindy(170, 2)：
- a.height == b.height (170 == 170)
- 执行 else 里的 return a.index < b.index; (0 < 2)，返回 true。
- sort 知道 a (Alice) 应该在 b (Cindy) 前面。

这样，std::sort 即使本身不稳定，也被我们“教会”了如何正确处理身高相同的情况，完美达成了题目的两个要求。

完整 C++ 代码 (带详细中文注释)

C++

#include <iostream> // 包含输入输出流库
#include <vector>   // 包含 vector (动态数组) 库
#include <algorithm> // 包含 sort (排序) 库
#include <string>   // 包含 string (字符串) 库

using namespace std; // 使用标准命名空间，省去写 std::

// 定义一个“人”的结构体，像一个信息包
struct Person {
    string name; // 姓名
    int height;  // 身高
    int index;   // 记录原始输入顺序（第几个输入的）
};

int main() {
    int n;
    cin >> n; // 读取人数

    // 创建一个 vector (可以自动扩容的数组)，用来存放 n 个 Person
    // vector<Person> people(n); 
    // 上面这行在某些旧编译器可能不行，下面这种写法更通用
    vector<Person> people; 
    people.resize(n); // 手动设置 vector 大小为 n

    // --- 步骤1：读取输入并记录原始顺序 ---
    for (int i = 0; i < n; ++i) {
        cin >> people[i].name >> people[i].height;
        people[i].index = i; // 关键：把循环变量 i (0, 1, 2...) 当作顺序存起来
    }

    // --- 步骤2：排序 ---
    // 调用 std::sort
    // 第一个参数: 排序的起始位置
    // 第二个参数: 排序的结束位置 (最后一个元素的下一个)
    // 第三个参数: 自定义的排序规则 (使用 Lambda 表达式)
    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        // 'a' 和 'b' 是 `sort` 拿来比较的两个人
        
        // 规则1：如果身高不相等
        if (a.height != b.height) {
            // 就按身高从低到高排
            // (返回 true，代表 a 应该排在 b 前面)
            return a.height < b.height;
        } 
        // 规则2：如果身高相等
        else {
            // 就按原始输入顺序 (index) 来排
            // (index 越小，说明输入越早，越排在前面)
            return a.index < b.index;
        }
    });

    // --- 步骤3：输出排序结果 ---
    // 使用 C++11 的 "基于范围的 for 循环" (Range-based for loop)
    // 'p' 会依次等于 people[0], people[1], ...
    // 'const auto&' 是一种高效的写法，表示“只读，不复制”
    for (const auto& p : people) {
        cout << p.name << endl; // 只输出名字，并换行
    }

    return 0; // 程序正常结束
}