【分数线划定】题解

题干信息解读
世博会志愿者选拔需根据计划录取人数的 150% 划定面试分数线，最终进入面试的是所有成绩不低于该分数线的选手。要求：
1.计算面试分数线（排名第⌊m×150%⌋名的分数）。
2.输出所有达到或超过该分数线的选手信息，按成绩降序、若成绩相同则按报名号升序排列。

整体做题思路
1.确定面试分数线：
①计算计划录取人数的 150% 并向下取整（如 m=3 时，150% 为 4.5，取整后为 4）。
②按成绩降序、报名号升序排序所有选手，取第⌊m×150%⌋名的分数作为分数线。
2.筛选并排序进入面试的选手：
①遍历所有选手，筛选出成绩≥分数线的人。
②对筛选后的选手再次排序（确保严格按成绩降序、报名号升序）。

数据结构选择：
1.使用vector存储选手信息，便于排序和遍历。
2.排序时需自定义比较函数，确保稳定性。

题目中的难点和注意事项
1.分数线的确定：
必须严格按排名而非分数值，即使有并列分数，也需按排名取对应位置的分数。
如样例中，第 4 名分数为 88，因此所有≥88 的选手（共 5 人）均进入面试。
2.排序规则：
1.两次排序需保持一致性：先按成绩降序，再按报名号升序。
2.若仅按成绩降序可能导致报名号乱序，需注意比较函数的实现。

边界处理：
输入保证⌊m×150%⌋ ≤ n，但需确保索引不越界。

AC代码（如有雷同，纯属巧合）

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

// 选手结构体：存储报名号和成绩
struct Candidate {
    int id;     // 报名号
    int score;  // 笔试成绩
};

// 自定义比较函数：成绩降序，若相同则报名号升序
bool cmp(const Candidate& a, const Candidate& b) {
    if (a.score != b.score) {
        return a.score > b.score;  // 成绩高的优先
    }
    return a.id < b.id;  // 成绩相同则报名号小的优先
}

int main() {
    int n, m;
    cin >> n >> m;

    // 读取所有选手信息
    vector<Candidate> candidates(n);
    for (int i = 0; i < n; ++i) {
        cin >> candidates[i].id >> candidates[i].score;
    }

    // 第一次排序：确定分数线
    sort(candidates.begin(), candidates.end(), cmp);

    // 计算面试分数线（注意索引从0开始）
    int lineIndex = m * 1.5 - 1;  // 第m×150%名的索引（向下取整）
    int lineScore = candidates[lineIndex].score;

    // 筛选所有成绩≥分数线的选手
    vector<Candidate> qualified;
    for (const auto& candidate : candidates) {
        if (candidate.score >= lineScore) {
            qualified.push_back(candidate);
        }
    }

    // 第二次排序：确保输出顺序严格符合要求
    sort(qualified.begin(), qualified.end(), cmp);

    // 输出结果
    cout << lineScore << " " << qualified.size() << endl;
    for (const auto& candidate : qualified) {
        cout << candidate.id << " " << candidate.score << endl;
    }

    return 0;
}

复杂度分析
时间复杂度：两次排序的时间复杂度均为 O (n log n)，遍历筛选的时间复杂度为 O (n)，总体时间复杂度为 O (n log n)，可高效处理 n≤5000 的数据规模。
空间复杂度：主要存储选手信息，空间复杂度为 O (n)，满足题目要求。