[NOIP2009 普及组] 分数线划定 题解 AC代码（C++）： 此处英文注释为自己靠着自己的英语知识使用百度翻译（fanyi.baidu.com/#zh/en/）所写，请酌情添加

这是本蒟蒻的第一篇题解 题目分析 题目的核心是计算面试分数线，并根据这个分数线筛选出进入面试的选手。具体步骤如下： 读取输入数据 首先，读取总选手数n和计划录取志愿者人数m。然后，读取每位选手的报名号和笔试成绩。 计算面试分数线 m计算面试分数线。面试分数线是排名第m * 150%（向下取整，函数floor(float a OR double b)）名的选手的分数。这意味着如果计划录取m名志愿者，那么排名在m * 150%以内（包括边界）的选手都能进入面试。 筛选和排序 根据面试分数线，筛选出所有笔试成绩不低于面试分数线的选手。然后，按照题目要求对这些选手的成绩进行排序：首先按成绩降序排序，如果成绩相同，则按报名号升序排序。 输出结果 首先输出面试分数线和实际进入面试的选手人数。然后，按照成绩（降序）和报名号（升序）顺序，输出这些选手的报名号和笔试成绩。 解题关键 排序算法的选择 使用常见的排序算法（如快速排序、归并排序等）或直接利用编程语言提供的排序函数sort。 数据结构的设计 为了方便地同时处理报名号和成绩，可以定义一个简单的结构体或类，或者使用两个并行数组（一个存储报名号，另一个存储成绩）。 精确控制排序规则 需要准确实现题目要求的排序规则——首先按成绩降序，再按报名号升序。 注意边界条件 特别是面试分数线的计算和重分情况的处理，需要仔细考虑。 代码环节 前面的题目解析你看了吗？ 就知道你没看，都是冲着答案来的，但也有例外 AC代码！AC，GO！ 其他没什么了，这篇题解到此结束

惊不惊喜，意不意外

话不多说，请看题解~

在最后，也祝大家早日AC!!!

#include <iostream> #include <vector> #include <algorithm> using namespace std; // 定义选手结构体 struct Candidate { int id; int score; }; // 自定义比较函数，用于排序 bool compare(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; }

解题步骤 我们首先可以定义一个结构体node，用来记录选手的报名号及笔试分数，并用数组 aaa 存储起来。由题意得：分数线是以 aaa 数组中，按每人的分数从高到低排序后，排名第 ⌊m∗1.5⌋\left\lfloor m*1.5 \right\rfloor⌊m∗1.5⌋ 的分数来划定的。我们可以记这个分数为 temptemptemp 。题目要求我们输出 temptemptemp 、分数 ≥temp≥temp≥temp 的总人数，以及所有 ≥temp≥temp≥temp 的人的报名号及其分数。定义完结构体和数组后，我们输入笔试人数 nnn 、预计人数 mmm ，以及每人的报名号 kkk 、分数 sss 。其次，我们将数组 aaa , 按每人的分数从高到低排序（如果分数相同，报名号越小的越前）。然后，我们定义一个类型为node的vector动态数组 vvv，用来记录被录取的人的报名号、分数（ vvv 的长度就是实际被录取的人数）。最后，输出 temptemptemp 、 vvv 的长度、 vvv 的每一项即可。 正解代码

题干信息解读 世博会志愿者选拔需根据计划录取人数的 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代码（如有雷同，纯属巧合） 复杂度分析 时间复杂度：两次排序的时间复杂度均为 O (n log n)，遍历筛选的时间复杂度为 O (n)，总体时间复杂度为 O (n log n)，可高效处理 n≤5000 的数据规模。 空间复杂度：主要存储选手信息，空间复杂度为 O (n)，满足题目要求。

A5. 分数线划定 - 题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目分析 本题需要根据规则确定面试分数线，并输出进入面试的选手信息。主要步骤包括： 1. 确定面试分数线位置：根据公式 position = floor(m * 1.5) 找到第几名选手的分数作为分数线 2. 筛选进入面试的选手：所有成绩不低于分数线的选手都进入面试 3. 排序规则： * 先按笔试成绩从高到低排序 * 成绩相同时，按报名号从小到大排序 解题思路 核心算法步骤 1. 数据存储：使用结构体存储每个选手的信息（报名号、成绩） 2. 排序：按照题目要求的排序规则进行排序 3. 确定分数线： * 计算分数线位置 line_index = floor(m * 1.5) - 1（数组下标从0开始） * 分数线分数为 scores[line_index].score 4. 统计实际人数：统计所有成绩不低于分数线的选手数量 5. 输出结果：按要求格式输出 时间复杂度 * 排序：O(n log n)，n ≤ 5000，完全可行 * 空间复杂度：O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++代码实现（ALL AC，可放心食用） 代码说明 关键点 1. 排序规则实现： 2. 分数线计算： * m * 1.5 得到理论位置（可能是小数） * floor() 向下取整得到整数位置 * 由于数组下标从0开始，需要减1：line_index = floor(m * 1.5) - 1 3. 实际人数统计： * 由于数组已按成绩降序排列，只需找到第一个成绩低于分数线的位置 * 使用 break 提前结束循环提高效率 样例解析 输入： 处理过程： 1. 计算分数线位置：floor(3 × 1.5) = floor(4.5) = 4，即第4名选手（下标3） 2. 排序后，下标3的选手成绩为88，所以分数线为88 3. 统计成绩≥88的选手：有5人 4. 输出结果 注意事项 1. 向下取整：必须使用 floor() 或整数除法实现向下取整 2. 数组下标：注意题目中的"第k名"与C++数组下标（从0开始）的转换 3. 边界情况：当分数线上有多人同分时，需要全部计入 4. 数据范围：n ≤ 5000，完全可以使用普通排序算法 复杂度分析 * 时间复杂度：O(n log n)，主要来自排序操作 * 空间复杂度：O(n)，存储选手信息 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总结 本题是一道简单的排序应用题，关键在于理解题目描述的排序规则和分数线划定方法。按照题目要求实现排序和筛选即可得到正确答案。 蒜鸟蒜鸟，睡了

(所有注释都在代码块里) AC代码

这道题目要求我们根据一定的规则来划定面试分数线，并输出进入面试的选手信息。下面是针对该题的C++代码实现： 代码解析 1. 数据结构：定义了一个Candidate结构体，包含报名号和笔试成绩。 2. 排序规则：自定义了compare函数，先按照笔试成绩降序排列，如果成绩相同，再按报名号升序排列。 3. 分数线计算：面试分数线对应的排名为m * 150 / 100，根据排序后的结果获取对应分数。 4. 筛选合格选手：从排序后的列表中，找到所有成绩不低于面试分数线的选手。 5. 输出结果：首先输出面试分数线和最终进入面试的人数，然后输出每个进入面试的选手信息。 这段代码能有效地解决该问题，并且保证输出的顺序和格式符合要求。

空降坐标：CP002689 来源：NOIP2009 普及组 请看代码

编者团队：https://www.acgo.cn/team/1894657430811287552

问题深度解析 核心规则梳理 面试分数线计算： 计算计划录取人数的150%，向下取整得到排名阈值k = floor(m * 1.5) 面试分数线为第k名选手的分数（从高到低排名） 所有成绩≥面试分数线的选手都进入面试 排序规则： 主要排序键：笔试成绩从高到低 次要排序键：报名号从小到大（成绩相同时） 关键注意事项 成绩相同的选手可能会导致实际进入面试的人数超过k 报名号是唯一的，可以作为成绩相同时的排序依据