题目链接

BGN21 分数线划定

题目描述

某市为世博会选拔志愿者，先进行笔试，再按笔试成绩划定面试分数线。规则如下：

  1. 计划最终录取 名志愿者。
  2. 面试名额定为 ，向下取整，记为 。
  3. 将所有报名号及笔试成绩按 成绩从高到低、成绩相同则报名号从小到大 的规则排序。
  4. 第 名选手的成绩即为面试分数线。
  5. 所有笔试成绩不低于该分数线的选手均进入面试。

请输出面试分数线及所有进入面试选手的信息（按排序后的顺序）。

输入描述

第一行输入两个整数 ，分别表示报名人数与计划录取人数。 接下来 行，每行输入两个整数 ，分别为报名号与笔试成绩。报名号保证唯一。

输出描述

第一行输出两个整数：面试分数线和进入面试的人数。 接下来若干行，按排序顺序输出每位进入面试的选手的报名号与成绩。

样例

输入

6 3
9848 90
6731 88
1422 95
7483 84
8805 95
4162 88

输出

88 5
1422 95
8805 95
9848 90
4162 88
6731 88

解题思路

本题的核心是对选手信息进行自定义排序，然后根据排序结果进行筛选。

1. 自定义排序 题目要求了双重排序规则：

  • 主关键字：成绩 score，按降序排列。
  • 次关键字：报名号 id，按升序排列（当成绩相同时）。

为了方便处理，我们可以将每个选手的信息（id 和 score）封装成一个结构体或类。然后，我们可以使用各语言内置的排序函数，并提供一个自定义的比较逻辑。

2. 确定分数线和面试名单

  • 首先，根据输入的 和 ，计算出面试名额 。
  • 对所有 名选手进行自定义排序。
  • 排序后，第 名选手（数组索引为 ）的成绩就是面试分数线 。
  • 再次遍历排序后的选手列表，所有成绩大于等于 的选手都进入面试。统计这些选手的人数，并按顺序输出他们的信息。

算法步骤：

  1. 读入 和 。
  2. 创建一个结构体/类数组，用于存储 名选手的 和 。
  3. 读入 名选手的信息。
  4. 实现一个自定义比较函数/逻辑，用于排序：
    • 如果两人分数不同，分数高的排前面。
    • 如果分数相同，id 小的排前面。
  5. 使用此逻辑对选手数组进行排序。
  6. 计算面试名额 。
  7. 获取分数线 ，即排序后第 名选手的成绩 sorted_candidates[k-1].score。
  8. 统计所有成绩 的选手数 。
  9. 输出 和 。
  10. 再次遍历排序后的数组，输出所有成绩 的选手的 和 。

代码

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

using namespace std;

struct Candidate {
    int id;
    int score;
};

bool compareCandidates(const Candidate& a, const Candidate& b) {
    if (a.score != b.score) {
        return a.score > b.score;
    }
    return a.id < b.id;
}

int main() {
    int n, m;
    cin >> n >> m;

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

    sort(candidates.begin(), candidates.end(), compareCandidates);

    int k = floor(m * 1.5);
    int line_score = candidates[k - 1].score;

    int count = 0;
    for (const auto& c : candidates) {
        if (c.score >= line_score) {
            count++;
        } else {
            break; // 因为已排序，后续分数只会更低
        }
    }

    cout << line_score << " " << count << '\n';

    for (int i = 0; i < count; ++i) {
        cout << candidates[i].id << " " << candidates[i].score << '\n';
    }

    return 0;
}

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

class Candidate {
    int id;
    int score;

    public Candidate(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();

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

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

        int k = (int) Math.floor(m * 1.5);
        int line_score = candidates[k - 1].score;

        int count = 0;
        for (Candidate c : candidates) {
            if (c.score >= line_score) {
                count++;
            } else {
                break;
            }
        }

        System.out.println(line_score + " " + count);

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

# -*- coding: utf-8 -*-
import math

n, m = map(int, input().split())
candidates = []
for _ in range(n):
    candidates.append(list(map(int, input().split())))

# 排序：分数降序，id升序
# 使用元组作为排序键，分数取负值来实现降序
candidates.sort(key=lambda x: (-x[1], x[0]))

k = math.floor(m * 1.5)
line_score = candidates[k - 1][1]

passed_candidates = []
for c in candidates:
    if c[1] >= line_score:
        passed_candidates.append(c)
    else:
        break

print(line_score, len(passed_candidates))
for c in passed_candidates:
    print(c[0], c[1])

算法及复杂度

  • 算法：自定义排序
  • 时间复杂度：，其中 是报名人数。主要开销来自于对所有选手进行排序。
  • 空间复杂度：，用于存储 名选手的报名信息。