[NOIP 2009 普及组] 分数线划定

题意

有 n 名选手，每人有报名号和分数。计划录取 m 人，面试分数线取排名第 floor(m * 1.5) 名选手的分数。

最终所有分数不低于分数线的人都进入面试，并按分数从高到低、报名号从小到大输出。

思路

先把选手按题目要求排序：

分数高的在前；
分数相同，报名号小的在前。

排序后，line_count = m * 3 // 2 就是题目中的 floor(m * 150%)。分数线是排序后第 line_count 个人的分数，也就是 Python 下标 line_count - 1。

因为可能有并列分数，所以不能只输出前 line_count 人，而要输出所有 score >= line_score 的选手。

Python 知识

people.sort(key=lambda item: (-item[1], item[0])) 是多关键字排序：分数用负号实现降序，报名号保持升序。
m * 3 // 2 用整数运算表达 floor(m * 1.5)，避免浮点数。
列表推导式 [item for item in people if item[1] >= line_score] 可以直接筛出达线选手。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import sys

data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
m = data[1]

people = []
index = 2
for _ in range(n):
    student_id = data[index]
    score = data[index + 1]
    people.append((student_id, score))
    index += 2

people.sort(key=lambda item: (-item[1], item[0]))
line_count = m * 3 // 2
line_score = people[line_count - 1][1]

chosen = [item for item in people if item[1] >= line_score]

print(line_score, len(chosen))
for student_id, score in chosen:
    print(student_id, score)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;

struct Player {
    int id;    // 报名号
    int score; // 分数
};

int n, m;
Player p[MAXN];

// 排序规则：分数降序，分数相同则报名号升序
bool cmp(const Player &a, const Player &b) {
    if (a.score != b.score) return a.score > b.score;
    return a.id < b.id;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> p[i].id >> p[i].score;
    }

    sort(p, p + n, cmp);

    int line_cnt = m * 3 / 2;          // 计划录取人数的 150%
    int line_score = p[line_cnt - 1].score; // 分数线

    // 统计所有达到分数线的选手
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (p[i].score >= line_score) cnt++;
    }

    cout << line_score << " " << cnt << "\n";
    for (int i = 0; i < cnt; i++) {
        cout << p[i].id << " " << p[i].score << "\n";
    }

    return 0;
}

复杂度

排序时间复杂度为 $O(n \log n)$ ，筛选时间复杂度为 $O(n)$ ，总时间复杂度为 $O(n \log n)$ 。空间复杂度为 $O(n)$ 。

总结

分数线由“排序后的某个位置”决定，输出人数由“所有达线者”决定，这两个数量不一定相同。

[NOIP 2009 普及组] 分数线划定

目录

题意

思路

Python 知识

代码

复杂度

总结