分数线划定

题目描述

世博会志愿者选拔中， $n$ 名选手（ $5 \le n \le 5000$ ）各有互不相同的报名号 $k$ （ $1000 \le k \le 9999$ ）和笔试成绩 $s$ （ $1 \le s \le 100$ ），计划录取 $m$ （ $3 \le m \le n$ ）名志愿者时，面试分数线为排名第 $\lfloor m \times 150 / 100 \rfloor$ 名选手的成绩，笔试成绩不低于分数线的选手都进入面试。输入第一行为 $n, m$ ，随后 $n$ 行每行两个整数 $k, s$ ；输出第一行为分数线和实际入面人数，随后每行一个入面选手的报名号和成绩，按成绩从高到低输出，成绩相同按报名号从小到大。样例输入 $n=6, m=3$ 及 1000 90 / 3239 88 / 2390 95 / 7231 84 / 1005 95 / 1001 88：第 $4$ 名成绩 $88$ 为分数线，同分选手一并入面，输出 88 5 加四行名单 1005 95 / 2390 95 / 1000 90 / 1001 88 / 3239 88。

思路

把 $n$ 名选手按「成绩降序、成绩相同报名号升序」排好序，第 $\lfloor m \times 150 / 100 \rfloor$ 名的成绩就是分数线。实际入面人数要按分数统计而不是直接用名次 $r$ ：与分数线同分的选手即使排名在 $r$ 之后也要一并纳入。排好序后入面者恰好构成序列前缀，读出分数线后统计并输出前缀即可。

参考代码

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
34#!/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-09-29 22:27
# update_at: 2026-09-29 22:30

import sys

RATIO = 150  # 面试线定在计划录取人数的 150% 名次上
FULL = 100   # 百分号的分母


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, admitted_plan = next(data), next(data)  # 题目中的 n、m
    players: list[tuple[int, int]] = [(next(data), next(data)) for _ in range(n)]

    # 成绩从高到低；成绩相同按报名号从小到大，元组比较正好就是这两级
    players.sort(key=lambda p: (-p[1], p[0]))

    # 面试线 = 第 floor(m*150/100) 名的成绩；同分者全部进入面试，实际人数可能超过该名次
    cut_rank = admitted_plan * RATIO // FULL
    # 个别数据里 floor(m*1.5) 会超出总人数，此时没人被淘汰，分数线记作 0（成绩至少为 1）
    line = players[cut_rank - 1][1] if cut_rank <= n else 0
    admitted = [p for p in players if p[1] >= line]

    out = [f"{line} {len(admitted)}"]
    out += [f"{k} {s}" for k, s in admitted]
    print('\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
59
60
61
62/**
 * 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-05 04:34
 * update_at: 2026-10-05 04:34
 */

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

typedef long long ll;

const int MAXN = 5005; // n <= 5000，多开几个下标防止越界

// 一名选手的排序所需信息
struct Player {
    ll id;    // 报名号
    ll score; // 笔试成绩
};

ll n, m;
Player p[MAXN]; // p[i] 表示第 i 名选手

// 排序规则：成绩从高到低，成绩相同报名号小的在前
bool cmp_player(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 (ll i = 1; i <= n; i++) {
        cin >> p[i].id >> p[i].score;
    }

    sort(p + 1, p + n + 1, cmp_player);

    // 分数线 = 排名 floor(m*150/100) 的选手成绩
    // 个别真实数据里 r 可能超过 n，此时按分数线 0 处理，所有人入面
    ll r = m * 150 / 100;
    ll line = 0;
    if (r <= n) line = p[r].score;

    // 实际人数按分数统计：与分数线同分的选手即使排名在 r 之后也要入面
    ll cnt = 0;
    for (ll i = 1; i <= n; i++) {
        if (p[i].score >= line) cnt++;
    }

    // 排好序后入面者恰好构成前缀，直接输出前 cnt 名
    cout << line << " " << cnt << "\n";
    for (ll i = 1; i <= cnt; i++) {
        cout << p[i].id << " " << p[i].score << "\n";
    }

    return 0;
}

目录

题目描述

思路

参考代码