[NOIP2009-普及] 分数线划定

题目描述

给定 $n$ 名选手的报名号 $k_i$ 与成绩 $s_i$ 。计划录取 $m$ 人，面试分数线为排名第 $\lfloor 1.5m \rfloor$ 的选手的分数，最终所有成绩不低于该分数线的选手进入面试。输出分数线、实际进面人数，以及进面选手按成绩降序、同分按报名号升序排列的名单。

数据范围： $5 \le n \le 5000$ ， $3 \le m \le n$ ， $1000 \le k_i \le 9999$ ， $1 \le s_i \le 100$ 。

思路

按 $(-成绩, 报名号)$ 排序后，第 $r = \lfloor 1.5m \rfloor$ 名的成绩即为分数线 $L$ ；再顺序输出所有 $s_i \ge L$ 的选手即可，重分扩招自动满足。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-10-02 08:12
# update_at: 2026-10-02 08:12

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    # 读入 (报名号, 成绩) 对
    people: list[tuple[int, int]] = [(next(data), next(data)) for _ in range(n)]

    # 成绩降序、成绩相同报名号升序：排序键直接取 (-成绩, 报名号)
    ranked: list[tuple[int, int]] = sorted(people, key=lambda p: (-p[1], p[0]))

    # 面试分数线 = 排名 floor(m*150%) 的选手分数（ranked 下标从 0 起）
    cutoff_rank = m * 3 // 2 - 1
    line = ranked[cutoff_rank][1]

    # 不低于分数线的全部进面试（含重分扩招）
    admitted: list[tuple[int, int]] = [p for p in ranked if p[1] >= line]

    out: list[str] = [f"{line} {len(admitted)}"]
    out += (f"{k} {s}" for k, s in admitted)
    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
54
55
56
57
58/**
 * 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-10-06 14:15
 * update_at: 2026-10-06 14:15
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 5005;

struct Person {
    int k; // 报名号
    int s; // 成绩
} a[MAXN];

int n, m;

// 成绩降序，成绩相同则报名号升序
bool cmp(const Person &x, const Person &y) {
    if (x.s != y.s) return x.s > y.s;
    return x.k < y.k;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].k >> a[i].s;
    }

    sort(a + 1, a + n + 1, cmp);

    int r = m * 3 / 2; // 向下取整后的排名位置（1-indexed）
    int line = a[r].s; // 面试分数线

    // 统计不低于分数线的实际人数
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i].s >= line) ++cnt;
    }

    cout << line << " " << cnt << "\n";
    for (int i = 1; i <= n; ++i) {
        if (a[i].s >= line) {
            cout << a[i].k << " " << a[i].s << "\n";
        }
    }

    return 0;
}

[NOIP2009-普及] 分数线划定

目录

题目描述

思路

参考代码