NOIP2009普及组真题解析：用C++三种排序方法搞定‘分数线划定’（附完整代码）

在信息学奥赛（NOIP/CSP）的备考过程中，排序算法是最基础也是最重要的知识点之一。2009年NOIP普及组的"分数线划定"题目，不仅考察了选手对排序算法的理解和应用能力，更提供了一个绝佳的机会来比较不同排序方法在实际问题中的表现。本文将通过这道经典题目，深入解析C++中三种不同的排序实现方案：标准库sort、手写冒泡排序以及计数排序+插入排序的组合应用。

1. 题目分析与解题思路

"分数线划定"题目要求根据考生的成绩和报名号，确定面试的分数线和进入面试的考生名单。具体规则是：面试人数为计划录取人数的150%（向下取整），然后所有成绩不低于该分数线的考生都将进入面试。如果有多人成绩相同，则按报名号升序排列。

这道题的核心在于 多重条件排序 ：首先按成绩降序排列，成绩相同则按报名号升序排列。对于最多5000个考生的数据规模，虽然O(n²)的排序算法也能胜任，但不同实现方式在代码复杂度、可读性和潜在性能上都有显著差异。

提示：在实际竞赛中，理解题目要求并选择合适的算法往往比直接编码更重要。建议先花1-2分钟仔细分析题目条件和数据范围。

2. 标准库sort解法：简洁高效的首选

C++标准库中的 sort 函数基于快速排序实现，平均时间复杂度为O(n log n)，是解决这类排序问题的首选方案。下面是使用 sort 的完整实现：

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

struct Student {
    int id, score;
};

bool compare(const Student &a, const Student &b) {
    return a.score != b.score ? a.score > b.score : a.id < b.id;
}

int main() {
    Student students[N];
    int n, m;
    cin >> n >> m;
    
    for(int i = 0; i < n; ++i)
        cin >> students[i].id >> students[i].score;
    
    sort(students, students + n, compare);
    
    int cutoff = students[(int)(m * 1.5) - 1].score;
    int count = 0;
    while(count < n && students[count].score >= cutoff)
        count++;
    
    cout << cutoff << " " << count << endl;
    for(int i = 0; i < count; ++i)
        cout << students[i].id << " " << students[i].score << endl;
    
    return 0;
}

这种实现方式的优势在于：

• 代码简洁 ：利用结构体和比较函数，清晰地表达了排序规则
• 性能优越 ：标准库sort经过高度优化，处理5000个元素几乎瞬间完成
• 可读性强 ：逻辑清晰，易于理解和维护

3. 手写冒泡排序：理解算法本质

虽然在实际比赛中很少需要手写排序算法，但通过实现冒泡排序可以深入理解排序的基本原理。下面是冒泡排序的实现：

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

int main() {
    int ids[N], scores[N], n, m;
    cin >> n >> m;
    
    for(int i = 0; i < n; ++i)
        cin >> ids[i] >> scores[i];
    
    // 冒泡排序实现
    for(int i = 0; i < n - 1; ++i) {
        for(int j = 0; j < n - 1 - i; ++j) {
            if(scores[j] < scores[j+1] || 
              (scores[j] == scores[j+1] && ids[j] > ids[j+1])) {
                swap(scores[j], scores[j+1]);
                swap(ids[j], ids[j+1]);
            }
        }
    }
    
    int cutoff = scores[(int)(m * 1.5) - 1];
    int count = 0;
    while(count < n && scores[count] >= cutoff)
        count++;
    
    cout << cutoff << " " << count << endl;
    for(int i = 0; i < count; ++i)
        cout << ids[i] << " " << scores[i] << endl;
    
    return 0;
}

冒泡排序的特点：

• 时间复杂度 ：O(n²)，对于n=5000来说，理论最大操作次数约为2500万次
• 稳定性 ：通过适当实现可以保证稳定性（相等元素相对顺序不变）
• 教学价值 ：帮助理解基本排序原理和交换操作

4. 计数排序+插入排序：特定场景的优化

当成绩范围有限（如0-100分）时，可以采用计数排序+插入排序的组合方案：

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

vector<int> students[101]; // 按分数分组存储报名号

int main() {
    int n, m, id, score;
    cin >> n >> m;
    
    for(int i = 0; i < n; ++i) {
        cin >> id >> score;
        // 使用插入排序保持每个分数段内报名号有序
        auto &group = students[score];
        auto it = lower_bound(group.begin(), group.end(), id);
        group.insert(it, id);
    }
    
    int total = 0, cutoff = 0;
    for(int s = 100; s >= 0; --s) {
        total += students[s].size();
        if(total >= m * 1.5) {
            cutoff = s;
            break;
        }
    }
    
    // 重新计算实际人数（可能有更多人达到cutoff分数）
    total = 0;
    for(int s = 100; s >= cutoff; --s)
        total += students[s].size();
    
    cout << cutoff << " " << total << endl;
    for(int s = 100; s >= cutoff; --s)
        for(int id : students[s])
            cout << id << " " << s << endl;
    
    return 0;
}

这种方法的优势在于：

• 线性时间复杂度 ：计数排序部分为O(n)，插入排序部分最坏O(n²)但实际表现良好
• 空间换时间 ：需要额外的存储空间来分组存储数据
• 适合特定场景 ：当分数范围有限且远小于n时效率最高

5. 三种方法的对比与选择

下表总结了三种实现方式的关键特点：

在实际竞赛中，建议优先考虑标准库sort方案，因为：

1. 开发效率高 ：减少编码时间，降低出错概率
2. 运行效率好 ：对于竞赛规模的数据足够高效
3. 可读性强 ：便于检查和调试

手写排序算法更适合以下场景：

• 学习算法原理时
• 需要特殊排序规则或优化时
• 在某些限制环境下（如不能使用STL）

计数排序+插入排序的组合则适用于数据具有特定分布特征（如分数范围有限）的情况。