🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

智能成绩表(100分)

🌍 评测功能需要 订阅专栏 后私信联系清隆解锁～

🍓OJ题目截图

🌲 智能成绩表

问题描述

K小姐是一位教师,她需要一个学生成绩管理系统来帮助她对学生的考试成绩进行排名。系统需要支持按照总分或者单科成绩进行排序。你能帮帮她吗?

输入格式

第一行包含两个正整数 $n$ 和 $m$,分别表示学生人数和科目数量。($0<n<100,0<m<10$)

第二行包含 $m$ 个由空格隔开的科目名称。科目名称只由英文字母构成,单个长度不超过 $10$ 个字符。科目的出现顺序和后续输入的学生成绩一一对应,不会出现重复的科目名称。

接下来的 $n$ 行,每行包含一个学生的姓名和该生 $m$ 个科目的成绩(空格隔开)。学生姓名只由英文字母构成,长度不超过 $10$ 个字符。成绩是 $0$ 到 $100$ 的整数,依次对应第二行输入的科目。

最后一行输入一个字符串,表示用作排名的科目名称。若该科目不存在,则按总分进行排序。

输出格式

输出一行,表示按成绩排序后的学生姓名,用空格隔开。如果有成绩相同的情况,则按照学生姓名的字典序进行排序。

样例输入

3 2
yuwen shuxue
fangfang 95 90
xiaohua 88 98
minmin 100 82
shuxue

样例输出

xiaohua fangfang minmin

样例输入

3 2
yuwen shuxue 
fangfang 95 90
xiaohua 88 95
minmin 90 95
zongfen

样例输出

fangfang minmin xiaohua

数据范围

• $0<n<100$
• $0<m<10$
• 科目名称和学生姓名均只由英文字母构成,长度不超过 $10$ 个字符。
• 成绩是 $0$ 到 $100$ 的整数。

题解

本题需要我们实现一个学生成绩管理系统,根据输入的学生信息和排序科目,输出按要求排序后的学生姓名。

首先,我们可以定义一个 Student 类来表示学生,包含学生姓名和一个排名要素列表。排名要素列表中,前 $m$ 个元素对应 $m$ 个科目的成绩,最后一个元素表示总分。

然后,我们读取输入并初始化学生列表。在读取科目信息时,我们可以用一个字典 subject_rankIdx 来存储科目名称到其在排名要素列表中的序号的映射关系。

接着,我们读取排序科目。如果该科目存在,我们取出其对应的序号 rankIdx,否则使用总分所在的序号 m。

最后,我们使用 sort 函数对学生列表进行排序。排序的 key 函数为一个 lambda 表达式,先比较 rank[rankIdx] 的值(降序),再比较学生姓名的字典序。

排序后,我们将学生姓名用空格连接并输出即可。

该方法的时间复杂度为 $O(n\log n)$,主要是排序的复杂度。空间复杂度为 $O(n)$,需要存储所有学生的信息。

参考代码

• Python

class Student:
    def __init__(self, name, rank):
        self.name = name
        self.rank = rank

n, m = map(int, input().split())
subject_rankIdx = {}
subjects = input().split()

for i in range(m):
    subject_rankIdx[subjects[i]] = i

students = []
for _ in range(n):
    data = input().split()
    name, scores = data[0], list(map(int, data[1:]))
    rank = scores + [sum(scores)]
    students.append(Student(name, rank))

subject = input()
rankIdx = subject_rankIdx.get(subject, m)

students.sort(key=lambda x: (-x.rank[rankIdx], x.name))
print(" ".join(stu.name for stu in students))

• Java

import java.util.*;

class Student {
    String name;
    int[] rank;

    Student(String name, int[] rank) {
        this.name = name;
        this.rank = rank;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        sc.nextLine(); // 消耗换行符

        Map<String, Integer> subjectRankIdx = new HashMap<>();
        String[] subjects = sc.nextLine().split(" ");
        for (int i = 0; i < m; i++) {
            subjectRankIdx.put(subjects[i], i);
        }

        List<Student> students = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] data = sc.nextLine().split(" ");
            String name = data[0];
            int[] scores = new int[m];
            for (int j = 0; j < m; j++) {
                scores[j] = Integer.parseInt(data[j + 1]);
            }
            int total = Arrays.stream(scores).sum();
            int[] rank = Arrays.copyOf(scores, m + 1);
            rank[m] = total;
            students.add(new Student(name, rank));
        }

        String subject = sc.nextLine();
        int rankIdx = subjectRankIdx.getOrDefault(subject, m);

        students.sort((a, b) -> {
            if (b.rank[rankIdx] != a.rank[rankIdx]) {
                return b.rank[rankIdx] - a.rank[rankIdx];
            } else {
                return a.name.compareTo(b.name);
            }
        });

        List<String> names = students.stream().map(stu -> stu.name).toList();
        System.out.println(String.join(" ", names));
    }
}

• Cpp

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

struct Student {
    string name;
    vector<int> rank;

    Student(string name, vector<int> rank) : name(name), rank(rank) {}
};

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

    unordered_map<string, int> subjectRankIdx;
    string subjects;
    getline(cin, subjects);
    stringstream ss(subjects);
    string subject;
    for (int i = 0; i < m; i++) {
        ss >> subject;
        subjectRankIdx[subject] = i;