信息学奥赛刷题笔记：用C++结构体+STL sort搞定OpenJudge NOI 1.10 01排名查询

在信息学奥赛的备战过程中，掌握高效的数据处理技巧至关重要。今天我们要探讨的是一道经典题目——OpenJudge NOI 1.10 01"谁考了第k名"，这道题看似简单，却蕴含着C++编程中几个核心概念：结构体定义、自定义排序规则以及STL算法的巧妙应用。

对于初学者来说，这道题提供了一个绝佳的机会，让我们能够从"读题-建模-实现-调试"的完整解题流程中，深入理解如何将实际问题转化为代码解决方案。更重要的是，通过对比手写排序算法与STL sort的实现方式，我们可以直观感受到标准库工具带来的代码简洁性和效率提升。

1. 题目分析与数据结构建模

1.1 理解题目需求

题目要求我们处理一组学生数据，每个学生有学号和分数两个属性，需要根据分数从高到低排序后，输出第k名学生的信息。看似简单的需求背后，我们需要考虑几个关键点：

• 数据规模：虽然示例数据量不大，但竞赛中需要考虑效率
• 排序规则：降序排列，分数高的在前
• 输出格式：学号和分数，分数可能需要特殊处理（如去除末尾多余的零）

1.2 选择合适的数据结构

在C++中，我们有多种方式可以表示学生数据：

// 方案1：使用结构体数组
struct Student {
    int id;
    double score;
};
Student students[100];

// 方案2：使用vector容器
vector<Student> students;

选择建议 ：

• 固定数量且已知上限时，数组更简单直接
• 数据量不确定或可能很大时，vector更灵活安全

2. 排序算法对比与选择

2.1 手写排序算法实现

我们先看看传统的排序方法如何解决这个问题：

// 冒泡排序实现
for(int i = 0; i < n-1; i++) {
    for(int j = 0; j < n-i-1; j++) {
        if(students[j].score < students[j+1].score) {
            swap(students[j], students[j+1]);
        }
    }
}

性能分析 ：

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 优点：实现简单，适合教学
• 缺点：效率低，不适合大规模数据

2.2 STL sort的优势

相比之下，STL的sort算法具有明显优势：

// 使用STL sort
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    return a.score > b.score; // 降序排列
});

关键优势 ：

• 时间复杂度：O(n log n)，效率显著提升
• 代码简洁：只需定义比较规则
• 稳定性：经过充分优化，适合竞赛环境

提示：在竞赛编程中，应优先使用标准库提供的算法，避免重复造轮子，这不仅能节省时间，还能减少出错概率。

3. 自定义排序规则的多种实现方式

3.1 重载小于运算符

在结构体内部重载运算符是最封装良好的方式：

struct Student {
    int id;
    double score;
    
    bool operator<(const Student& other) const {
        return score > other.score; // 注意是降序
    }
};

// 使用时直接调用sort
sort(students, students + n);

3.2 使用独立比较函数

对于需要多种排序方式的情况，独立函数更灵活：

bool compareStudents(const Student& a, const Student& b) {
    return a.score > b.score;
}

// 使用时传入比较函数
sort(students.begin(), students.end(), compareStudents);

3.3 Lambda表达式（C++11及以上）

现代C++推荐使用lambda表达式，尤其是一次性比较逻辑：

sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    return a.score > b.score;
});

方法对比表 ：

方法	适用场景	优点	缺点
运算符重载	固定排序规则	调用简洁	不够灵活
独立函数	多种排序需求	可复用	需要额外定义
Lambda	一次性使用	灵活方便	不能复用

4. 完整解题流程与代码实现

4.1 输入处理与边界检查

良好的编程习惯应从输入处理开始：

int n, k;
cin >> n >> k;
if(k < 1 || k > n) {
    cerr << "Invalid k value" << endl;
    return 1;
}

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

4.2 排序实现

选择最优的排序方式：

// 使用lambda表达式实现降序排序
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    return a.score > b.score;
});

4.3 输出处理

注意题目对输出格式的要求：

// 直接使用cout输出，会自动处理浮点数格式
cout << students[k-1].id << " " << students[k-1].score;

注意：vector下标从0开始，所以第k名对应索引k-1

4.4 完整代码示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Student {
    int id;
    double score;
};

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<Student> students(n);
    for(int i = 0; i < n; i++) {
        cin >> students[i].id >> students[i].score;
    }
    
    sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        return a.score > b.score;
    });
    
    cout << students[k-1].id << " " << students[k-1].score;
    
    return 0;
}

5. 调试技巧与常见问题

5.1 常见错误排查

1. 下标越界 ：忘记vector从0开始，导致k-1可能为负
2. 排序方向错误 ：降序写成升序
3. 浮点数比较 ：直接使用==比较浮点数可能不准确

5.2 测试用例设计

好的测试用例应覆盖各种边界情况：

• 最小规模：n=1, k=1
• 最大规模：n=100, k=100
• 极端值：所有分数相同
• 随机数据：验证排序正确性

示例测试数据 ：

// 测试数据1：常规情况
5 3
1001 95.5
1002 88.0
1003 92.5
1004 90.0
1005 89.5

// 测试数据2：所有分数相同
3 2
2001 85.0
2002 85.0
2003 85.0

// 测试数据3：最小规模
1 1
3001 99.9

5.3 性能优化建议

虽然这道题数据量不大，但养成性能意识很重要：

1. 使用reserve预先分配vector空间
2. 避免不必要的拷贝（使用引用传参）
3. 考虑使用更快的IO方式（如scanf/printf或关闭同步）

// 提升IO速度的技巧
ios::sync_with_stdio(false);
cin.tie(nullptr);

6. 扩展思考与实际应用

6.1 多条件排序

实际问题中经常需要多级排序，例如分数相同按学号升序：

sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    if(a.score != b.score)
        return a.score > b.score;
    return a.id < b.id;
});

6.2 结构体设计进阶

更复杂的数据结构设计：

struct ExamResult {
    int student_id;
    string name;
    double score;
    int rank;
    // 可以添加更多字段和方法
};

6.3 STL算法的其他应用

除了sort，其他有用的算法：

// 查找特定分数段的学生
auto it = find_if(students.begin(), students.end(), [](const Student& s) {
    return s.score >= 90.0;
});

// 统计及格人数
int pass_count = count_if(students.begin(), students.end(), [](const Student& s) {
    return s.score >= 60.0;
});

在实际竞赛中，这类数据处理题目非常常见。掌握结构体和STL算法的组合使用，可以大幅提升解题效率。我曾在一次模拟赛中遇到类似题目，当时因为不熟悉sort的自定义比较而浪费了大量时间手写排序，结果不仅代码冗长，还引入了难以发现的bug。从那以后，我深刻认识到标准库工具的重要性。