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

#include<iostream> #include<stdio.h> using namespace std; int main(){ int m,n; cin >> n >> m; int a[2][n]; m *= 1.5; for(int c=0 ;c<n; c++){ cin >> a[0][c] >> a[1][c]; } for(int c=0; c<n; c++){ for(int z=n-1; z > c; z--){ if(a[0][z]<a[0][z-1]){ swap(a[1][z],a[1][z-1]); swap(a[0][z],a[0][z-1]); } } } for(int c=0; c<n; c++){ for(int z=n-1; z > c; z--){ if(a[1][z]>a[1][z-1]){ swap(a[1][z],a[1][z-1]); swap(a[0][z],a[0][z-1]); } } } int c=m-1; for (; c<(n-1) && a[1][c] == a[1][c+1]; ++c); }

#include <bits/stdc++.h> using namespace std; int s[105],k[10005][105]; int main(void) { int n,m,ss,kk,count = 0,i,max = 0,x,j; scanf("%d%d",&n,&m); m = m * 1.5; for (i = 0;i < n;i++) { scanf("%d%d",&kk,&ss); k[kk][ss]; s[ss]; } for (i = 100;count < m;i--) count += s[i]; printf("%d %d\n",i + 1,count); x = i + 1; for(i = 100;i >= x;i--) for(j = 1000;j <= 10000;j++) if(k[j][i]) printf("%d %d\n",j,i); return 0; }

code

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

#include<iostream> #include<stdio.h> using namespace std; int main(){ int m,n; cin >> n >> m; int a[2][n]; m *= 1.5; for(int c=0 ;c<n; c++){ cin >> a[0][c] >> a[1][c]; } for(int c=0; c<n; c++){ for(int z=n-1; z > c; z--){ if(a[0][z]<a[0][z-1]){ swap(a[1][z],a[1][z-1]); swap(a[0][z],a[0][z-1]); } } } for(int c=0; c<n; c++){ for(int z=n-1; z > c; z--){ if(a[1][z]>a[1][z-1]){ swap(a[1][z],a[1][z-1]); swap(a[0][z],a[0][z-1]); } } } int c=m-1; for (; c<(n-1) && a[1][c] == a[1][c+1]; ++c); }

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

惊不惊喜，意不意外

#include <bits/stdc++.h> //导入万能工具箱 using namespace std; int main(){ int m,n; cin >> n >> m; int a[2][n]; m *= 1.5; for(int c=0 ;c<n; c++){ cin >> a[0][c] >> a[1][c]; } for(int c=0; c<n; c++){ for(int z=n-1; z > c; z--){ if(a[0][z]<a[0][z-1]){ swap(a[1][z],a[1][z-1]); swap(a[0][z],a[0][z-1]); } } } for(int c=0; c<n; c++){ for(int z=n-1; z > c; z--){ if(a[1][z]>a[1][z-1]){ swap(a[1][z],a[1][z-1]); swap(a[0][z],a[0][z-1]); } } } int c=m-1; for (; c<(n-1) && a[1][c] == a[1][c+1]; ++c); cout << a[1][c] << " " << c + 1 << endl; for(int i=0;i<=c;i++){ cout<<a[0][i]<<" "<<a[1][i]<<endl; } }

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

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

#include <future> #include <algorithm> using namespace std; struct information{ int k,s; bool operator<(information v){ if(s!=v.s) return s>v.s; return k<v.k; } }a[5001];int n,m; int main(){ scanf("%d%d",&n,&m); m+=m/2; for(int i=1;i<=n;i++)scanf("%d%d",&a[i].k,&a[i].s); sort(a+1,a+n+1); for(int i=m+1;a[i].s==a[m].s&&i<=n;i++)m++; printf("%d %d\n",a[m].s,m); for(int i=1;i<=m;i++)printf("%d %d\n",a[i].k,a[i].s); }

#include<iostream> #include<stdio.h> using namespace std; int main(){ int m,n; cin >> n >> m; int a[2][n]; m *= 1.5; for(int c=0 ;c<n; c++){ cin >> a[0][c] >> a[1][c]; } for(int c=0; c<n; c++){ for(int z=n-1; z > c; z--){ if(a[0][z]<a[0][z-1]){ swap(a[1][z],a[1][z-1]); swap(a[0][z],a[0][z-1]); } } } for(int c=0; c<n; c++){ for(int z=n-1; z > c; z--){ if(a[1][z]>a[1][z-1]){ swap(a[1][z],a[1][z-1]); swap(a[0][z],a[0][z-1]); } } } int c=m-1; for (; c<(n-1) && a[1][c] == a[1][c+1]; ++c); cout << a[1][c] << " " << c + 1 << endl; for(int i=0;i<=c;i++){ cout<<a[0][i]<<" "<<a[1][i]<<endl; } }

解题步骤 我们首先可以定义一个结构体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)，满足题目要求。

话不多说，请看题解~