E卷-刷题笔记合集🔗

选修课

问题描述

现有两门选修课，每门选修课都有一部分学生选修，每个学生都有选修课的成绩。需要找出同时选修了两门选修课的学生，并按照以下规则进行排序和输出：

1. 首先按照班级进行划分，班级编号小的先输出。
2. 每个班级内部，按照两门选修课成绩和的降序排序。
3. 成绩相同时，按照学生的学号升序排序。

输入格式

输入包含两行：

1. 第一行为第一门选修课学生的成绩。
2. 第二行为第二门选修课学生的成绩。

每行数据中，学生之间以英文分号分隔，每个学生的学号和成绩以英文逗号分隔。

学生学号的格式为 8 位数字：2 位院系编号 + 入学年份后 2 位 + 院系内部 1 位专业编号 + 所在班级 3 位学号。

输出格式

输出同时选修了两门选修课的学生的学号。如果没有同时选修两门选修课的学生，输出 NULL。

否则，按照以下格式输出：

1. 先输出班级编号（学号前五位）。
2. 然后另起一行输出这个班级同时选修两门选修课的学生学号，学号之间以英文分号分隔。
3. 不同班级之间用换行符分隔。

样例输入1

01202021,75;01201033,95;01202008,80;01203006,90;01203088,100
01202008,70;01203088,85;01202111,80;01202021,75;01201100,88

样例输出1

01202
01202008;01202021
01203
01203088

样例输入2

01201022,75;01202033,95;01202018,80;01203006,90;01202066,100
01202008,70;01203102,85;01202111,80;01201021,75;01201100,88

样例输出2

NULL

样例解释

数据范围

• 学生成绩的取值范围为 之间的整数。
• 两门选修课选修学生数的取值范围为 之间的整数。

题解

排序+模拟

这道题目的核心在于如何高效地处理学生数据并按照要求进行排序。解决这个问题的关键步骤如下：

1. 数据解析： 首先需要从输入中解析出学生的信息。可以使用字典（哈希表）来存储学生信息，以学号为键，值包含班级、两门课的成绩等信息。这样可以快速判断一个学生是否选修了两门课，并方便后续的处理。

2. 筛选同时选修两门课的学生： 遍历所有学生，检查是否有两门课的成绩。这一步可以在解析数据时同时进行，提高效率。

3. 按班级分组： 使用另一个字典，以班级编号为键，值为该班级所有同时选修两门课的学生列表。

4. 排序： 对每个班级的学生列表进行排序。排序的关键在于自定义比较函数，先比较总成绩（降序），再比较学号（升序）。

5. 输出结果： 按照班级编号的顺序输出结果。如果没有符合条件的学生，输出"NULL"。

这个解法的时间复杂度主要来自于排序步骤，为 O(nlogn)，其中 n 是学生的总数。考虑到题目给出的数据范围（学生数不超过 2000），这个复杂度是可以接受的。

参考代码

非常抱歉之前的回答不完整。以下是完整的参考代码和用于生成测试数据的代码：

• Python

def process_students(course1, course2):
    # 创建字典存储学生信息
    students = {}
    
    # 处理第一门课程的学生信息
    for student in course1.split(';'):
        id, score = student.split(',')
        students[id] = {'class': id[:5], 'score1': int(score), 'score2': -1}
    
    # 处理第二门课程的学生信息
    for student in course2.split(';'):
        id, score = student.split(',')
        if id in students:
            students[id]['score2'] = int(score)
        else:
            students[id] = {'class': id[:5], 'score1': -1, 'score2': int(score)}
    
    # 筛选同时选修两门课的学生
    selected_students = {id: info for id, info in students.items() if info['score1'] != -1 and info['score2'] != -1}
    
    if not selected_students:
        return "NULL"
    
    # 按班级分组
    classes = {}
    for id, info in selected_students.items():
        class_id = info['class']
        if class_id not in classes:
            classes[class_id] = []
        classes[class_id].append((id, info['score1'] + info['score2']))
    
    # 排序并生成输出
    result = []
    for class_id in sorted(classes.keys()):
        result.append(class_id)
        students_in_class = sorted(classes[class_id], key=lambda x: (-x[1], x[0]))
        result.append(';'.join(student[0] for student in students_in_class))
    
    return '\n'.join(result)

# 读取输入
course1 = input().strip()
course2 = input().strip()

# 处理数据并输出结果
print(process_students(course1, course2))

• C

// 待补充

• Javascript

function processStudents(course1, course2) {
    const students = new Map();
    
    course1.split(';').forEach(student => {
        const [id, score] = student.split(',');
        students.set(id, { class: id.slice(0, 5), score1: parseInt(score), score2: -1 });
    });
    
    course2.split(';').forEach(student => {
        const [id, score] = student.split(',');
        if (students.has(id)) {
            students.get(id).score2 = parseInt(score);
        } else {
            students.set(id, { class: id.slice(0, 5), score1: -1, score2: parseInt(score) });
        }
    });
    
    const selectedStudents = new Map([...students].filter(([_, info]) => info.score1 !== -1 && info.score2 !== -1));
    
    if (selectedStudents.size === 0) {
        return "NULL";
    }
    
    const classes = new Map();
    selectedStudents.forEach((info, id) => {
        if (!classes.has(info.class)) {
            classes.set(info.class, []);
        }
        classes.get(info.class).push([id, info.score1 + info.score2]);
    });
    
    const result = [];
    [...classes.keys()].sort().forEach(classId => {
        result.push(classId);
        const studentsInClass = classes.get(classId).sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0]));
        result.push(studentsInClass.map(s => s[0]).join('