NOIP2009普及组真题解析：用C++的sort函数搞定‘分数线划定’，附四种解法对比

在信息学奥赛的备战过程中，排序算法是每位选手必须掌握的核心技能。2009年NOIP普及组的"分数线划定"题目，不仅考察了基础的排序能力，更考验选手对不同排序算法特性的理解。这道题的数据规模虽然不大（最多5000条记录），但恰恰适合用来深入探讨各种排序方法的优劣。

本文将带你从零开始拆解这道经典题目，重点分析C++标准库中 sort 函数的灵活应用，同时对比结构体排序、冒泡排序、计数排序+插入排序、stable_sort稳定排序四种实现方案。不同于简单的AC题解，我们会深入探讨每种算法的时间复杂度、适用场景和编码技巧，帮助你在竞赛中根据数据特征快速选择最优解法。

1. 题目分析与解题思路

"分数线划定"的题目要求可以简化为：给定n个考生的报名号和成绩，按照成绩从高到低排序，成绩相同时按报名号从小到大排序。然后确定录取分数线为排名第m*1.5（向下取整）的考生成绩，最后输出所有不低于该分数线的考生信息。

关键解题步骤 ：

1. 数据输入 ：存储每个考生的报名号和成绩
2. 自定义排序 ：
   • 主排序键：成绩降序
   • 次排序键：报名号升序
3. 分数线计算 ：取第⌊m*1.5⌋个考生的成绩
4. 结果输出 ：统计并输出所有不低于分数线的考生

注意：题目中的m 1.5需要向下取整，C++中可以直接使用int(m 1.5)实现。

这道题的数据规模n≤5000，意味着O(n²)的算法（如冒泡排序）也能在规定时间内完成。但在实际竞赛中，养成使用高效算法的习惯非常重要，因为题目数据范围可能会在后续年份调整。

2. 结构体排序：最清晰的解法

使用结构体存储考生信息，配合自定义比较函数，是最直观的解决方案。这种方法代码可读性强，易于维护，是竞赛中的首选方案。

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

struct Student {
    int id, score;
};

bool compare(const Student &a, const Student &b) {
    if(a.score != b.score)
        return a.score > b.score;  // 成绩降序
    return a.id < b.id;            // 报名号升序
}

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

性能分析 ：

• 时间复杂度：O(n log n)，来自 sort 函数
• 空间复杂度：O(n)，存储所有考生信息
• 优点：代码简洁，逻辑清晰，适合各种规模的数据
• 缺点：需要额外定义结构体和比较函数

3. 冒泡排序：理解排序本质

虽然在实际竞赛中不推荐使用冒泡排序，但通过实现它可以帮助我们深入理解排序算法的基本原理。下面是使用冒泡排序的解法：

#include <iostream>
using namespace std;
#define N 5005

int main() {
    int ids[N], scores[N];
    int 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-i-1; ++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)];
    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万次
• 空间复杂度：O(n)
• 优点：不依赖STL，有助于理解排序原理
• 缺点：效率低，在大数据量时可能超时

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

当成绩范围有限时（如本题中成绩≤100），可以采用计数排序+插入排序的混合策略。这种方法在成绩分布集中的情况下效率极高。

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

vector<int> scoreBuckets[101];  // 0-100分

int main() {
    int n, m;
    cin >> n >> m;
    
    for(int i = 0; i < n; ++i) {
        int id, score;
        cin >> id >> score;
        // 使用插入排序保持每个桶内id有序
        auto &bucket = scoreBuckets[score];
        auto it = bucket.begin();
        while(it != bucket.end() && *it < id)
            ++it;
        bucket.insert(it, id);
    }
    
    int cutoff = 0, count = 0;
    for(int s = 100; s >= 0; --s) {
        count += scoreBuckets[s].size();
        if(count >= int(m * 1.5)) {
            cutoff = s;
            break;
        }
    }
    
    // 重新计算精确的count
    count = 0;
    for(int s = 100; s >= cutoff; --s)
        count += scoreBuckets[s].size();
    
    cout << cutoff << " " << count << endl;
    for(int s = 100; s >= cutoff; --s)
        for(int id : scoreBuckets[s])
            cout << id << " " << s << endl;
    
    return 0;
}

性能分析 ：

• 时间复杂度：O(n + k)，其中k是成绩范围（101）
• 空间复杂度：O(n + k)
• 优点：当k<<n时，效率极高
• 缺点：成绩范围大时空间消耗大，且实现较复杂

5. stable_sort两阶段排序：保持稳定性的方案

如果需要保持排序稳定性（即相同键值的元素保持原有顺序），可以使用 stable_sort 进行两阶段排序：

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

struct Student {
    int id, score;
};

bool compareId(const Student &a, const Student &b) {
    return a.id < b.id;
}

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

int main() {
    Student stu[N];
    int n, m;
    cin >> n >> m;
    
    for(int i = 0; i < n; ++i)
        cin >> stu[i].id >> stu[i].score;
    
    // 先按id排序，保证相同score时id小的在前
    stable_sort(stu, stu + n, compareId);
    // 再按score排序，保持相同score元素的相对顺序
    stable_sort(stu, stu + n, compareScore);
    
    int cutoff = stu[int(m * 1.5)].score;
    int count = 0;
    while(count < n && stu[count].score >= cutoff)
        count++;
    
    cout << cutoff << " " << count << endl;
    for(int i = 0; i < count; ++i)
        cout << stu[i].id << " " << stu[i].score << endl;
    
    return 0;
}

性能分析 ：

• 时间复杂度：O(n log n)，但常数因子比普通sort大
• 空间复杂度：O(n)
• 优点：保持排序稳定性，适合需要保持相对顺序的场景
• 缺点：需要两次排序，效率略低

6. 四种解法对比与选择策略

为了帮助大家在实际竞赛中快速选择合适的方法，我们总结四种解法的特点：

解法	时间复杂度	空间复杂度	编码复杂度	适用场景
结构体+sort	O(n log n)	O(n)	低	通用场景，推荐首选
冒泡排序	O(n²)	O(n)	中	教学用途，实际竞赛不推荐
计数+插入	O(n + k)	O(n + k)	高	成绩范围小(k小)时高效
stable_sort	O(n log n)	O(n)	中	需要保持稳定性的场景

在实际比赛中，建议优先考虑结构体+sort的方案，它提供了最佳的平衡点：代码简洁、效率高、可读性好。只有当题目有特殊要求（如明确需要稳定性或数据范围特殊）时，才考虑其他方案。

选择排序算法的几个考量因素 ：

1. 数据规模：n的大小直接影响算法选择
2. 数据特性：是否部分有序、键值范围等
3. 稳定性要求：是否需要保持相同键值的相对顺序
4. 空间限制：是否有严格的内存限制
5. 编码时间：竞赛中时间宝贵，选择实现快速的方案

在NOIP/CSP等竞赛中，掌握 sort 函数的灵活应用可以解决80%以上的排序需求。建议重点练习结构体排序方法，并理解比较函数的编写规则。