分数线划定

思路

这题说白了就是个排序 + 模拟。先把题目拆解一下：

有 n 个人参加笔试，计划录取 m 人进面试
面试分数线怎么定？取排名第 $\lfloor m \times 150\% \rfloor$ 名选手的成绩作为分数线
所有成绩 大于等于 分数线的选手都能进面试（所以实际人数可能超过计划数）

那关键问题来了——怎么排序？

题目要求按成绩从高到低排，成绩相同则按报名号从小到大。排好之后，找到第 $\lfloor m \times 1.5 \rfloor$ 个人的成绩就是分数线。

但这里有个细节：可能有多个人和分数线同分。这些人全部要进面试，所以最终进面试的人数可能比 $\lfloor m \times 1.5 \rfloor$ 多。

实现上很直接：

读入数据，自定义排序
算出 $pos = \lfloor m \times 1.5 \rfloor$ ，取 $a[pos-1]$ 的成绩作为分数线
遍历统计所有成绩 $\geq$ 分数线的人数，输出即可

因为排好序之后，所有 $\geq$ 分数线的人一定连续排在前面，直接输出前 cnt 个人就行。

代码

C++
Java
Python3
JavaScript

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> a(n); // {id, score}
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    // 按成绩降序，成绩相同按报名号升序
    sort(a.begin(), a.end(), [](const pair<int,int>& x, const pair<int,int>& y) {
        if (x.second != y.second) return x.second > y.second;
        return x.first < y.first;
    });
    int pos = (int)(m * 1.5); // floor(m * 150%)
    if (pos > n) pos = n;
    int scoreLine = a[pos - 1].second;
    // 统计所有 >= 分数线的人数
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i].second >= scoreLine) cnt++;
    }
    cout << scoreLine << " " << cnt << endl;
    for (int i = 0; i < cnt; i++) {
        cout << a[i].first << " " << a[i].second << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = sc.nextInt(); // id
            a[i][1] = sc.nextInt(); // score
        }
        // 按成绩降序，成绩相同按报名号升序
        Arrays.sort(a, (x, y) -> {
            if (x[1] != y[1]) return y[1] - x[1];
            return x[0] - y[0];
        });
        int pos = (int)(m * 1.5); // floor(m * 150%)
        if (pos > n) pos = n;
        int scoreLine = a[pos - 1][1];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (a[i][1] >= scoreLine) cnt++;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(scoreLine).append(" ").append(cnt).append("\n");
        for (int i = 0; i < cnt; i++) {
            sb.append(a[i][0]).append(" ").append(a[i][1]).append("\n");
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = []
for _ in range(n):
    id_, score = map(int, input().split())
    a.append((id_, score))

# 按成绩降序，成绩相同按报名号升序
a.sort(key=lambda x: (-x[1], x[0]))

pos = int(m * 1.5)
if pos > n:
    pos = n
score_line = a[pos - 1][1]

cnt = sum(1 for _, s in a if s >= score_line)
print(score_line, cnt)
for i in range(cnt):
    print(a[i][0], a[i][1])

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [n, m] = lines[0].split(' ').map(Number);
    const a = [];
    for (let i = 0; i < n; i++) {
        const [id, score] = lines[i + 1].split(' ').map(Number);
        a.push([id, score]);
    }
    // 按成绩降序，成绩相同按报名号升序
    a.sort((x, y) => {
        if (x[1] !== y[1]) return y[1] - x[1];
        return x[0] - y[0];
    });
    let pos = Math.floor(m * 1.5);
    if (pos > n) pos = n;
    const scoreLine = a[pos - 1][1];
    let cnt = 0;
    for (let i = 0; i < n; i++) {
        if (a[i][1] >= scoreLine) cnt++;
    }
    const out = [];
    out.push(scoreLine + ' ' + cnt);
    for (let i = 0; i < cnt; i++) {
        out.push(a[i][0] + ' ' + a[i][1]);
    }
    console.log(out.join('\n'));
});

复杂度分析

时间复杂度: $O(n \log n)$ ，瓶颈在排序。
空间复杂度: $O(n)$ ，存储所有选手信息。

小结

这是一道典型的排序模拟题，没有什么复杂的数据结构或算法。核心就两步：自定义排序 + 按规则找分数线。唯一容易踩坑的地方是同分选手的处理——分数线位置上可能有多个同分的人，这些人全部要算进去，所以最终人数不一定等于 $\lfloor m \times 1.5 \rfloor$ 。想清楚这一点，代码写起来就很顺了。

题解 | #分数线划定#

分数线划定

思路

代码

复杂度分析

小结