1168 分数线划定
大约 3 分钟
1168 分数线划定
【算法】 排序
【C++】 sort、结构体、cmp 比较函数、floor
【难度】 入门
一、题目简述
世博会志愿者选拔:有 名选手(),计划录取 人()。
面试分数线 = 排名第 名的选手的分数。
进入面试:笔试成绩不低于面试分数线的所有选手。最终按成绩从高到低输出,成绩相同按报名号从小到大。
二、解题思路
2.1 核心步骤
- 计算面试人数:(即
m * 3 / 2在整数运算中等价于 ) - 排序:按成绩降序,成绩相同按报名号升序
- 确定分数线:第 名的成绩即为分数线
- 确定实际人数:从第 名开始往后扫描,只要成绩 ≥ 分数线就继续加入
2.2 分数线的理解
"面试分数线为排名第 名的选手的分数"
假设 ,则 ,第 4 名的分数即为分数线。
但可能有并列:如果第 4 名分数 = 88,第 5 名也是 88,则第 5 名也进入面试。这就是"最终进入面试的选手为笔试成绩不低于面试分数线的所有选手"的含义。
2.3 手动模拟样例
输入:,计算
| 报名号 | 成绩 |
|---|---|
| 1000 | 90 |
| 3239 | 88 |
| 2390 | 95 |
| 7231 | 84 |
| 1005 | 95 |
| 1001 | 88 |
排序后:
| 排名 | 报名号 | 成绩 |
|---|---|---|
| 1 | 1005 | 95 |
| 2 | 2390 | 95 |
| 3 | 1000 | 90 |
| 4 | 1001 | 88 |
| 5 | 3239 | 88 |
| 6 | 7231 | 84 |
- 第 4 名分数 = 88 → 分数线 = 88
- 第 5 名也是 88(≥ 分数线),所以也进入面试
- 实际进入面试人数 = 5 人
三、参考代码
#include <bits/stdc++.h>
using namespace std;
struct Student {
int id, score;
};
bool cmp(Student a, Student b) {
if (a.score != b.score)
return a.score > b.score; // 成绩降序
return a.id < b.id; // 报名号升序
}
int main() {
int n, m;
cin >> n >> m;
Student a[5005];
for (int i = 0; i < n; i++) {
cin >> a[i].id >> a[i].score;
}
sort(a, a + n, cmp);
int k = m * 3 / 2; // 等价于 floor(m * 1.5)
int line = a[k - 1].score; // 第 k 名的分数(下标 k-1)
// 统计实际进入面试的人数
int cnt = k;
while (cnt < n && a[cnt].score >= line) {
cnt++;
}
cout << line << " " << cnt << endl;
for (int i = 0; i < cnt; i++) {
cout << a[i].id << " " << a[i].score << endl;
}
return 0;
}为什么
m * 3 / 2等于 ?
整数运算中m * 3 / 2先乘 3 再整除 2。由于 是整数,,整数除法自动向下取整。
四、复杂度分析
- 时间复杂度:,排序主导。,排序约 万次比较,瞬间完成。
- 空间复杂度:,存储 个选手信息。
五、易错点
- 分数线取第 名,不是第 名:,写成
m * 3 / 2即可。 - 下标处理:第 名在排序后的数组中下标是 。
- 并列分数要全部输出:分数线之后的选手如果分数等于分数线也要进入面试,所以需要
while循环向后扫描。 - 用整数算:
m * 3 / 2等价于 。写成m * 1.5会引入浮点误差,不推荐。
