用C++解NOIP真题：P1068分数线划定，从冒泡到STL sort的四种解法对比

在信息学奥赛（NOIP/CSP）的备战过程中，排序算法是每位选手必须掌握的核心技能。2009年NOIP普及组的《分数线划定》一题，看似简单却暗藏玄机——它要求选手在处理多重排序规则时，能够灵活选择最优解法。这道题的数据规模虽然不大（最多5000条记录），但恰恰为我们提供了绝佳的教学案例：从最基础的冒泡排序开始，逐步升级到STL的高阶用法，甚至探索混合算法的可能性。

对于初学者而言，这道题的价值不仅在于"AC"（通过测试），更在于理解不同解法的适用场景与性能差异。本文将带您深入剖析四种典型解法：传统冒泡排序、结构体结合STL sort、两趟稳定排序（stable_sort）以及计数排序与插入排序的混合应用。每种方法都有其独特的实现逻辑和优化思路，我们将从代码复杂度、执行效率、内存占用等多个维度进行对比，帮助您在竞赛中做出更明智的选择。

1. 基础解法：冒泡排序的双重条件实现

让我们从最朴素的冒泡排序开始。虽然在实际竞赛中很少会真正使用这种O(n²)的算法，但理解它的实现原理对夯实基础至关重要。在分数线划定问题中，我们需要先按成绩降序排列，成绩相同时再按报名号升序排列——这种双重条件的排序规则，正是考察的重点。

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

int main() {
    int k[N], s[N], n, m, line, ct = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) 
        cin >> k[i] >> s[i];
    
    // 冒泡排序核心逻辑
    for(int i = 1; i <= n - 1; ++i)
        for(int j = 1; j <= n - i; ++j) {
            if(s[j] < s[j+1] || (s[j] == s[j+1] && k[j] > k[j+1])) {
                swap(s[j], s[j+1]);
                swap(k[j], k[j+1]);
            }
        }
    
    line = s[int(m*1.5)];
    for(int i = 1; i <= n; ++i) 
        if(s[i] >= line) ct++;
    
    cout << line << ' ' << ct << endl;
    for(int i = 1; i <= ct; ++i)
        cout << k[i] << ' ' << s[i] << endl;
    return 0;
}

关键点解析：

• 双重条件判断： s[j] < s[j+1] || (s[j] == s[j+1] && k[j] > k[j+1]) 这一行代码完美体现了题目要求的排序规则
• 交换逻辑：当条件满足时，需要同时交换成绩和报名号两个数组的值
• 时间复杂度：最坏情况下需要进行约5000×5000=25,000,000次比较和交换

提示：虽然冒泡排序在本题数据规模下仍能通过，但在实际竞赛中应尽量避免使用，除非题目明确限制算法选择。

2. 结构体与STL sort的优雅解法

当数据需要关联多个属性时，结构体是C++中最自然的表达方式。结合STL的sort算法，我们可以写出更简洁、更易维护的代码。这种解法的核心在于自定义比较函数，它决定了排序的规则。

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

struct Stu {
    int k, s; // k:报名号 s:成绩
};

bool cmp(Stu &a, Stu &b) {
    if(a.s == b.s)         // 分数相同时
        return a.k < b.k;  // 报名号小的在前
    else                   // 分数不同时
        return a.s > b.s;  // 成绩高的在前
}

int main() {
    Stu stu[N];
    int n, m, line, ct = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> stu[i].k >> stu[i].s;
    
    sort(stu+1, stu+1+n, cmp); // 使用自定义比较函数排序
    
    line = stu[int(m*1.5)].s;
    for(int i = 1; i <= n; ++i)
        if(stu[i].s >= line) ct++;
    
    cout << line << ' ' << ct << endl;
    for(int i = 1; i <= ct; ++i)
        cout << stu[i].k << ' ' << stu[i].s << endl;
    return 0;
}

性能对比：

指标	冒泡排序	STL sort
时间复杂度	O(n²)	O(nlogn)
代码复杂度	中等	简单
内存占用	较低	中等
可维护性	较差	优秀
适用数据规模	<1万	无限制

这种解法的优势不仅在于性能提升，更在于代码的可读性和扩展性。如果需要添加新的排序条件，只需修改cmp函数即可，主逻辑完全不受影响。

3. 稳定排序的应用：两趟排序策略

在某些特殊场景下，我们需要保持相同关键字的原始顺序，这时stable_sort就派上用场了。虽然本题并不严格要求稳定性，但了解这种解法有助于拓宽思路。

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

struct Stu {
    int k, s;
};

bool cmp_k(const Stu &a, const Stu &b) {
    return a.k < b.k; // 报名号升序
}

bool cmp_s(const Stu &a, const Stu &b) {
    return a.s > b.s; // 成绩降序
}

int main() {
    Stu stu[N];
    int n, m, line, ct = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> stu[i].k >> stu[i].s;
    
    // 先按次要条件排序，再按主要条件稳定排序
    stable_sort(stu+1, stu+1+n, cmp_k);
    stable_sort(stu+1, stu+1+n, cmp_s);
    
    line = stu[int(m*1.5)].s;
    for(int i = 1; i <= n; ++i)
        if(stu[i].s >= line) ct++;
    
    cout << line << ' ' << ct << endl;
    for(int i = 1; i <= ct; ++i)
        cout << stu[i].k << ' ' << stu[i].s << endl;
    return 0;
}

稳定排序的特点：

• 保持相等元素的相对顺序
• 时间复杂度同样是O(nlogn)，但常数因子通常比sort大
• 适用于需要多次排序且要保持前次排序结果的场景
• 在本题中，先按报名号排序，再按成绩稳定排序，等价于单次多条件排序

注意：虽然两趟排序能得到正确结果，但在竞赛中应优先考虑单次多条件排序，除非题目明确要求保持稳定性。

4. 混合算法：计数排序+插入排序的巧妙组合

当数据范围有限时（如本题成绩不超过100分），计数排序可以发挥O(n)的时间复杂度优势。结合插入排序处理同分学生的报名号排序，这种混合算法在特定条件下性能最优。

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

int score[105][5005] = {}; // score[i][0]存储长度

int main() {
    int k, s, n, m, line, ct = 0;
    cin >> n >> m;
    
    // 计数排序+插入排序
    for(int i = 1; i <= n; ++i) {
        cin >> k >> s;
        // 将k插入score[s]数组，并保持升序
        int& len = score[s][0];
        score[s][++len] = k;
        for(int j = len; j > 1; --j) {
            if(score[s][j] < score[s][j-1])
                swap(score[s][j], score[s][j-1]);
            else break;
        }
    }
    
    // 确定分数线
    int lnum = int(m*1.5);
    for(int i = 100; i >= 0; --i) {
        ct += score[i][0];
        if(ct >= lnum) {
            line = i;
            break;
        }
    }
    
    cout << line << ' ' << ct << endl;
    // 输出结果
    for(int i = 100; i >= line; --i)
        for(int j = 1; j <= score[i][0]; ++j)
            cout << score[i][j] << ' ' << i << endl;
    return 0;
}

算法分析：

• 计数排序部分：O(n)时间复杂度处理成绩分布
• 插入排序部分：最坏情况下O(k²)，k为同分人数，但本题中k≤5000
• 空间复杂度：O(max_score×n)，当成绩范围很大时不适用
• 优势：当成绩范围小而n很大时，效率远超常规排序算法

适用场景判断：

情况描述	推荐算法
成绩范围小(如0-100)，n很大	计数+插入排序
成绩范围大，n中等(≤10⁵)	STL sort单次排序
需要保持相同成绩的原始顺序	stable_sort两趟
算法限制(如禁用STL)	冒泡或其他基础排序

5. 竞赛中的实战选择策略

在真实的NOIP/CSP竞赛环境中，选择哪种解法不仅取决于算法效率，还需要考虑以下因素：

代码实现速度：

• 结构体+sort写法通常最快实现
• 冒泡排序虽然效率低，但在时间紧迫时可能更快写出
• 混合算法实现复杂，容易出错，适合有充分时间检查时使用

调试难度：

1. 结构体解法：变量组织清晰，调试最容易
2. 两趟排序：需要注意排序顺序是否正确
3. 混合算法：多维数组操作容易出界，需要仔细检查
4. 冒泡排序：虽然简单，但边界条件容易出错

鲁棒性考量：

• STL sort经过充分优化，几乎不会出现性能问题
• 自己实现的排序需要注意特殊测试用例：
  • 所有成绩相同
  • 所有报名号相同
  • 极端数据(如n=1或n=5000)

// 竞赛推荐写法示例
#include <bits/stdc++.h>
using namespace std;

struct Candidate {
    int id, score;
    bool operator<(const Candidate& rhs) const {
        return score != rhs.score ? score > rhs.score : id < rhs.id;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<Candidate> candidates(n);
    for(auto& c : candidates) cin >> c.id >> c.score;
    
    sort(candidates.begin(), candidates.end());
    
    int cutoff = candidates[(int)(m*1.5)-1].score;
    int count = count_if(candidates.begin(), candidates.end(), 
        [cutoff](const Candidate& c) { return c.score >= cutoff; });
    
    cout << cutoff << ' ' << count << '\n';
    for(int i = 0; i < count; ++i)
        cout << candidates[i].id << ' ' << candidates[i].score << '\n';
}

优化技巧：

• 使用vector替代原生数组更安全
• 重载operator<比单独写cmp函数更简洁
• 使用count_if算法统计人数更符合现代C++风格
• 统一使用标准输入输出流（关闭同步后可提速）

在实际比赛中，我通常会准备一个排序算法的模板代码，遇到需要排序的题目时，只需根据具体需求调整比较逻辑即可。这种标准化的工作流程可以大幅减少实现时间，把更多精力留给真正的算法难题。