题解 | #分数线划定#

题目链接

分数线划定

题目描述

某市选拔志愿者，共 $n$ 人报名，计划录取 $m$ 人。选拔过程如下：

面试名额定为计划录取人数的1.5倍，即 $m \cdot 1.5$ ，结果向下取整。
所有报名者按笔试成绩从高到低排序，如果成绩相同，则按报名号从小到大排序。
排序后，第 面试名额 位的选手的成绩，即为本次面试的分数线。
所有笔试成绩不低于该分数线的选手，均可进入面试。

请输出最终的面试分数线、进入面试的总人数，以及所有进入面试的选手信息。

解题思路

本题是一个典型的排序应用题。我们需要根据题目给定的多重规则对选手信息进行处理，并最终筛选出合格的选手。

核心步骤如下：

数据结构：首先，需要一个结构来存储每位选手的信息，至少包含报名号 id 和成绩 score。
计算面试名额：根据规则，面试名额数量 interview_slots 等于 $\lfloor m \cdot 1.5 \rfloor$ 。
排序：这是本题的关键。我们需要对所有 $n$ 名选手进行排序。
- 主排序键：成绩 score，按降序排列。
- 次排序键：报名号 id，按升序排列。在实现时，如果 a.score > b.score，则 a 排在前面。如果 a.score == b.score，则比较报名号，若 a.id < b.id，a 排在前面。
确定分数线：排序后，我们找到第 interview_slots 名选手（数组下标为 interview_slots - 1）。该选手的成绩就是面试分数线 score_line。
统计合格人数：确定分数线后，我们需要再次遍历排序后的列表，找出所有成绩大于或等于 score_line 的选手。由于列表已经按成绩降序排列，我们可以从头开始遍历，直到遇到第一个成绩小于 score_line 的选手为止。所有在此之前的选手都合格。
输出结果：
- 第一行输出 score_line 和合格人数。
- 随后逐行输出所有合格选手的 id 和 score。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Applicant {
    int id;
    int score;
};

bool compareApplicants(const Applicant& a, const Applicant& 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(NULL);

    int n, m;
    cin >> n >> m;

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

    sort(applicants.begin(), applicants.end(), compareApplicants);

    int interview_slots = floor(m * 1.5);
    int score_line = applicants[interview_slots - 1].score;

    int qualified_count = 0;
    for (const auto& app : applicants) {
        if (app.score >= score_line) {
            qualified_count++;
        } else {
            break;
        }
    }

    cout << score_line << " " << qualified_count << endl;
    for (int i = 0; i < qualified_count; ++i) {
        cout << applicants[i].id << " " << applicants[i].score << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

class Applicant {
    int id;
    int score;

    public Applicant(int id, int score) {
        this.id = id;
        this.score = score;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Applicant[] applicants = new Applicant[n];
        for (int i = 0; i < n; i++) {
            applicants[i] = new Applicant(sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(applicants, new Comparator<Applicant>() {
            @Override
            public int compare(Applicant a, Applicant b) {
                if (a.score != b.score) {
                    return b.score - a.score; // 降序
                }
                return a.id - b.id; // 升序
            }
        });

        int interviewSlots = (int) Math.floor(m * 1.5);
        int scoreLine = applicants[interviewSlots - 1].score;

        int qualifiedCount = 0;
        for (Applicant app : applicants) {
            if (app.score >= scoreLine) {
                qualifiedCount++;
            } else {
                break;
            }
        }

        System.out.println(scoreLine + " " + qualifiedCount);
        for (int i = 0; i < qualifiedCount; i++) {
            System.out.println(applicants[i].id + " " + applicants[i].score);
        }
    }
}

import math

n, m = map(int, input().split())
applicants = []
for _ in range(n):
    # 将id和score作为元组存入列表
    applicants.append(tuple(map(int, input().split())))

# 使用lambda函数进行排序
# -x[1]实现按分数降序，x[0]实现按id升序
applicants.sort(key=lambda x: (-x[1], x[0]))

interview_slots = math.floor(m * 1.5)
score_line = applicants[interview_slots - 1][1]

qualified_applicants = []
for app in applicants:
    if app[1] >= score_line:
        qualified_applicants.append(app)
    else:
        break

print(score_line, len(qualified_applicants))
for app in qualified_applicants:
    print(app[0], app[1])

算法及复杂度

算法：排序
时间复杂度：主要开销来自于对 $n$ 个选手进行排序，因此时间复杂度为 $\mathcal{O}(n \log n)$ 。
空间复杂度：需要一个数组或列表来存储所有 $n$ 名选手的信息，因此空间复杂度为 $\mathcal{O}(n)$ 。