[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; }

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)，存储选手信息 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总结 本题是一道简单的排序应用题，关键在于理解题目描述的排序规则和分数线划定方法。按照题目要求实现排序和筛选即可得到正确答案。 蒜鸟蒜鸟，睡了

解题步骤 我们首先可以定义一个结构体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 的每一项即可。 正解代码

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

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

题干信息解读 世博会志愿者选拔需根据计划录取人数的 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)，满足题目要求。

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

点赞的是我义父

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

其实我也陷进去了（坑） 一开始我是这样的（标上我的思路） 可是 只有#2和#3是对的 我又把floor改成ceil 只对一个#1 然后我想 “分数线给了，报名号在后面的几位且分数等于分数线的不能录取，不公平呀！” 于是我又把代码改了 正解来了！ 我们在排完序之后把报名号在后面的几位且分数等于分数线的几位也加进来，也就是 然后就像原来的那样输出就可以了 完整代码