题目链接

最厉害的学生

题目描述

给定 名学生及其三门课的成绩（语文、数学、英语）。你需要找出总分最高的学生，并输出他/她的姓名和三门课的成绩。

  • 平分规则：如果有多名学生的总分并列最高，则选择其中输入顺序最靠前的学生。

输入描述:

  • 第一行包含一个整数 （）。
  • 接下来 行，每行包含一个字符串（学生姓名）和三个整数（语文、数学、英语成绩）。

输出描述:

  • 输出一行，包含总分最高学生的姓名和他的三门成绩，用空格隔开。

示例 输入:

4
alice 100 90 80
david 90 100 80
mary 80 80 100
bob 100 90 80

输出:

alice 100 90 80

说明: alice 和 bob 的总分均为270，但 alice 的输入顺序更早，因此输出 alice。

解题思路

这是一个典型的查找最值问题，附带了一个简单的平分处理规则。我们可以通过一次遍历就找到答案。

  1. 维护最优解：

    • 我们需要几个变量来实时记录"到目前为止最厉害的学生"的信息。
    • max_total_score：记录当前找到的最高总分，可以初始化为 -1。
    • best_student_name, best_chinese, best_math, best_english：记录对应最高分学生的姓名和各科成绩。

  2. 单次遍历:

    • 我们从头到尾遍历输入的 个学生。
    • 对于每个学生，我们读取其信息并计算总分 current_total。
    • 然后，将 current_total 与 max_total_score 进行比较。
    • 关键点：如果 current_total > max_total_score，我们就更新 max_total_score 为 current_total，并用当前学生的信息更新所有 best_ 系列变量。
    • 注意，由于我们只在分数严格大于时才更新，如果遇到一个总分相同的学生，best_ 变量不会被覆盖。这就自然而然地满足了"平分时取输入顺序最早者"的规则。

  3. 最终结果:

    • 当遍历完所有 个学生后，best_ 系列变量中存储的就是最终答案。我们只需按格式输出它们即可。

这种单遍扫描的算法时间复杂度为 ，空间复杂度为 （只使用了常数个额外变量），非常高效。

代码

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    string best_name;
    int best_chinese = -1, best_math = -1, best_english = -1;
    int max_total_score = -1;

    for (int i = 0; i < n; ++i) {
        string name;
        int chinese, math, english;
        cin >> name >> chinese >> math >> english;

        int current_total = chinese + math + english;
        if (current_total > max_total_score) {
            max_total_score = current_total;
            best_name = name;
            best_chinese = chinese;
            best_math = math;
            best_english = english;
        }
    }

    cout << best_name << " " << best_chinese << " " << best_math << " " << best_english << endl;

    return 0;
}

import java.util.Scanner;

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

        String bestName = "";
        int bestChinese = -1, bestMath = -1, bestEnglish = -1;
        int maxTotalScore = -1;

        for (int i = 0; i < n; i++) {
            String name = sc.next();
            int chinese = sc.nextInt();
            int math = sc.nextInt();
            int english = sc.nextInt();

            int currentTotal = chinese + math + english;
            if (currentTotal > maxTotalScore) {
                maxTotalScore = currentTotal;
                bestName = name;
                bestChinese = chinese;
                bestMath = math;
                bestEnglish = english;
            }
        }

        System.out.println(bestName + " " + bestChinese + " " + bestMath + " " + bestEnglish);
        sc.close();
    }
}

def main():
    n = int(input())
    
    max_total_score = -1
    best_student_info = None
    
    for _ in range(n):
        line = input().split()
        name = line[0]
        chinese = int(line[1])
        math = int(line[2])
        english = int(line[3])
        
        current_total = chinese + math + english
        
        if current_total > max_total_score:
            max_total_score = current_total
            best_student_info = (name, chinese, math, english)
            
    print(*best_student_info)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 单遍扫描查找最大值
  • 时间复杂度: ，因为我们只需要遍历一次所有 个学生。
  • 空间复杂度: ，我们只需要常数个变量来存储最优解的信息，空间使用不随 的增长而增长。