文章目录

• PAT 甲级 1012 The Best Rank (25 分)（Java）
• • 题目
  • 大体题意
  • 解题思路
  • 解法
  • • 解法一

PAT 甲级 1012 The Best Rank (25 分)（Java）

题目

题目链接

大体题意

一组学生成绩，每个学生分别有c语言、数学、英语三门课的成绩以及三门课的平均成绩，每门课都一个相应排名，现在需要知道指定学生的四门成绩中排名最靠前的一门成绩及相应的排名，优先级按照平均成绩> c > 数学 > 英语

解题思路

1. 首先需要一个学生类，有学号、四门课的成绩、四门课各自的排名、四门课最优排名的索引；
2. 分别对每门课进行排序并确认相应的排名；
3. 获取每个学生四门课中的最优排名；
4. 通过数组将学号和在学生数组中的位置进行映射，通过空间换时间以O（1）的时间复杂度获取当前学生是否存在；

注：输入需要使用StreamTokenizer；

解法

解法一

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;

class Student{
    public int number; // 学号
    public int[] grade; // 分数数组
    public int[] rank; // 排名数组
    public int best; // 最佳排名
}

public class Main {

    static int flag = 0; // 分数数组排序列的索引，如flag = 0是对平均分进行排序

    public static void main(String[] args) throws IOException {
        StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        sc.nextToken();
        int n = (int)sc.nval;
        sc.nextToken();
        int m = (int)sc.nval;
        Student[] data = new Student[n];
        int[] exist = new int[1000001]; // 映射数组，判断当前学号是否存在以及在Student数组中的位置
        char[] subject = new char[]{'A', 'C', 'M', 'E'};
        for (int i=0; i<n; ++i){
            data[i] = new Student();
            data[i].grade = new int[4];
            data[i].rank = new int[4];
            sc.nextToken();
            data[i].number = (int)sc.nval;
            sc.nextToken();
            data[i].grade[1] = (int)sc.nval;
            sc.nextToken();
            data[i].grade[2] = (int)sc.nval;
            sc.nextToken();
            data[i].grade[3] = (int)sc.nval;
            data[i].grade[0] = ( data[i].grade[1] +  data[i].grade[2] +  data[i].grade[3]) / 3;
        }
        for(int i=0; i<4; ++i){
            flag = i;
            Arrays.sort(data, new Comparator<Student>() {
                @Override
                public int compare(Student o1, Student o2) {
                    return o2.grade[flag] - o1.grade[flag] ;
                }
            });
            // 平均分或学科分数的排名情况
            data[0].rank[flag] = 1;
            for (int j = 1; j < n; j++) {
                if(data[j].grade[flag] == data[j-1].grade[flag]){
                    data[j].rank[flag] = data[j-1].rank[flag];
                }else{
                    data[j].rank[flag] = j + 1;
                }
            }
        }
        // 获取每个人最优的排名情况
        for (int i = 0; i < n; i++) {
            int k = 0;
            int min = data[i].rank[0];
            exist[data[i].number] = i + 1;
            for (int j = 1; j < 4; j++) {
                if(min > data[i].rank[j]){
                    min = data[i].rank[j];
                    k = j;
                }
            }
            data[i].best = k;
        }

        for (int i = 0; i < m; i++) {
            sc.nextToken();
            int id = (int)sc.nval;
            flag = exist[id];
            if(flag > 0){
                System.out.println(data[flag-1].rank[data[flag-1].best] + " " + subject[data[flag-1].best]);
            }else{
                System.out.println("N/A");
            }
        }
    }
}