• 【Java】PAT(Basic Level) Practice(中文) 1015德才论

    前言

    ※  PTA是 程序设计类实验辅助教学平台 ，里边包含一些编程题目集以供练习。

    这道题用java解一定会超时，在文章结语部分我会证明。我用java试了四种解法，不断优化，但始终是三个测试点通过、三个测试点超时。我把我的代码放在这里，做个参考吧。文章最后附有C语言解法。

    1015 德才论 题目

        题目    

    作者 CHEN, Li

    单位 浙江大学

    宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”：“是故才德全尽谓之圣人，才德兼亡谓之愚人，德胜才谓之君子，才胜德谓之小人。凡取人之术，苟不得圣人，君子而与之，与其得小人，不若得愚人。”

    现给出一批考生的德才分数，请根据司马光的理论给出录取排名。

    输入格式：

    输入第一行给出 3 个正整数，分别为：N（≤10^5），即考生总数；L（≥60），为录取最低分数线，即德分和才分均不低于 L 的考生才有资格被考虑录取；H（<100），为优先录取线——德分和才分均不低于此线的被定义为“才德全尽”，此类考生按德才总分从高到低排序；才分不到但德分到优先录取线的一类考生属于“德胜才”，也按总分排序，但排在第一类考生之后；德才分均低于 H，但是德分不低于才分的考生属于“才德兼亡”但尚有“德胜才”者，按总分排序，但排在第二类考生之后；其他达到最低线 L 的考生也按总分排序，但排在第三类考生之后。

    随后 N 行，每行给出一位考生的信息，包括：准考证号 德分 才分，其中准考证号为 8 位整数，德才分为区间 [0, 100] 内的整数。数字间以空格分隔。

    输出格式：

    输出第一行首先给出达到最低分数线的考生人数 M，随后 M 行，每行按照输入格式输出一位考生的信息，考生按输入中说明的规则从高到低排序。当某类考生中有多人总分相同时，按其德分降序排列；若德分也并列，则按准考证号的升序输出。

    输入样例：

    1. 14 60 80
    2. 10000001 64 90
    3. 10000002 90 60
    4. 10000011 85 80
    5. 10000003 85 80
    6. 10000004 80 85
    7. 10000005 82 77
    8. 10000006 83 76
    9. 10000007 90 78
    10. 10000008 75 79
    11. 10000009 59 90
    12. 10000010 88 45
    13. 10000012 80 100
    14. 10000013 90 99
    15. 10000014 66 60

    输出样例：

    1. 12
    2. 10000013 90 99
    3. 10000012 80 100
    4. 10000003 85 80
    5. 10000011 85 80
    6. 10000004 80 85
    7. 10000007 90 78
    8. 10000006 83 76
    9. 10000005 82 77
    10. 10000002 90 60
    11. 10000014 66 60
    12. 10000008 75 79
    13. 10000001 64 90

     

    Java代码    

    我用java写了四种解法，测试结果都是三个测试点正确、三个测试点超时。研究半天也没搞明白到底为什么超时，大概是Java本身的速度不足吧。代码就发出来做个参考吧。

    解法一  

    首先，用二维数组存储所有学生信息，每个一维数组存储一个学生的信息。我用这个数组作为静态链表来排序（定义一个int作为头指针），每个学生的信息后都有一个int值指向排序下一名的学生的角标。最后打印时降序输出即可。要注意处理链表第一名的特殊情况，以及学生排序的逻辑。代码如下。

    测试结果：三个测试点正确，另外三个测试点超时。

    1. /*
    2. 功能：根据规则对给定考生成绩进行排序并输出
    3. 实现思路：用数组存储每个考生的信息，并且用数组作为静态链表实现排序。
    4. 时间复杂度   空间复杂度
    5. */
    6. import java.io.*;
    7. class Main{
    8.     public static void main(String[] args) throws IOException{
    9.         //接收输入
    10.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    11.         String[] arr1 = br.readLine().split(" +");
    12.         int n = Integer.parseInt(arr1[0]);    //考生总数
    13.         int l = Integer.parseInt(arr1[1]);    //最低录取分数线
    14.         int h = Integer.parseInt(arr1[2]);    //优秀录取线
    15.         //在线排序
    16.         int[][] a = new int[n][6];    //数组每一行代表一个考生，存储考号、德分、才分、总分、等级、链表序号
    17.         int m = 0;            //录取总人数
    18.         String[] b = new String[3];    //接收当前考生的信息
    19.         int yi = -1;            //已录取学生排序链表中的第一名的角标
    20.         for(int i=0;i//在线处理每个考生的信息
    21.             b = br.readLine().split(" +");    //接收当前考生的信息
    22.             a[i][0] = Integer.parseInt(b[0]);        //将考生信息转为int
    23.             a[i][1] = Integer.parseInt(b[1]);
    24.             a[i][2] = Integer.parseInt(b[2]);
    25.             a[i] = getGrade(a[i],l,h);    //调用函数填写总分及等级信息，排序地址初始化
    26.             if(a[i][4]<5){                //若是第一~第四类考生
    27.                 m++;                        //则录取
    28.                 a = getSort(a,i,yi);           //调用函数填写链表地址信息
    29.                 if(a[i][5]==yi)            //判断是否要更新第一名的角标
    30.                     yi = i;
    31.             }
    32.         }
    33.         //打印输出
    34.         System.out.print(m);    //输出录取总人数
    35.         if(m==0)    return;        //若是录取人数为0，则直接返回
    36.         String stu = "";
    37.         for(int i=yi;;i=a[i][5]){    //按数组静态链表的排序，以成绩降序输出
    38.             stu = "\n" + a[i][0] + " " +a[i][1] + " " + a[i][2];
    39.             System.out.print(stu);
    40.             if(a[i][5]==-1)    //若是链表中录取的最后一名
    41.                 break;            //则跳出循环，停止打印
    42.         }
    43.         
    44.         
    45.     }
    46.     private static int[] getGrade(int[] a,int l,int h){
    47.         //功能：根据数组中学生成绩，填写总分及等级信息 。l是录取线，h是优秀线。
    48.         a[3] = a[1] + a[2];    //计算总分
    49.         a[5] = -1;             //排序地址信息初始化
    50.         if(a[1]2]//若德才有一项未达到录取线
    51.             a[4] = 5;        //第五类考生，不予录取
    52.             return a;
    53.         }
    54.         if(a[1]>=h && a[2]>=h){    //若德才均优秀
    55.             a[4] = 1;        //第一类考生
    56.             return a;
    57.         }
    58.         if(a[1]>=h){        //若德分优秀而才分不优秀
    59.             a[4] = 2;        //第二类考生
    60.             return a;
    61.         }    
    62.         if(a[1]>=a[2]){    //若德分不优秀，但德分≥才分
    63.             a[4] = 3;        //第三类考生
    64.             return a;
    65.         }
    66.         a[4] = 4;            //其它考生为第四类考生
    67.         return a;
    68.     }
    69.     private static int[][] getSort(int[][] a,int t,int yi){
    70.         //功能：对数组中指定学生的成绩（以数组静态链表方式）排序并返回数组
    71.         //参数 a[][] 学生信息数组 ；t 待排序学生角标 ；yi 已排序的录取学生链表中第一名学生角标
    72.         if(yi==-1)                    //如果链表中还没有学生
    73.             return a;                   //则以待排序学生作为第一名，直接返回
    74.         if(gradeCompare(a[t],a[yi])){        //如果待排序的学生是新的第一名
    75.             a[t][5] = yi;                //待排序学生链接指向原先的第一名
    76.             return a;
    77.         }
    78.         for(int i=yi,j=i;;i=a[i][5]){      //若链表中已经有至少一名学生，则正常进行排序
    79.             if(gradeCompare(a[i],a[t])){    //若待排序学生成绩<当前对比学生成绩
    80.                 j=i;                            //用j记住当前对比学生角标
    81.                 if(a[i][5]==-1){                //若当前对比学生已经是最后一名
    82.                     a[i][5] = t;                    //将待排序学生插入到链表结尾
    83.                     break;                          //排序完毕，退出循环
    84.                 }
    85.             }
    86.             else{                          //若待排序学生成绩>当前对比学生成绩
    87.                 a[j][5] = t;                    //上一名的学生链接到待排序学生
    88.                 a[t][5] = i;                    //待排序学生链接到当前对比学生
    89.                 break;                            //排序完毕，退出循环
    90.             }
    91.         }  
    92.         return a;
    93.     }
    94.     private static boolean gradeCompare(int[] a,int[] b){
    95.         //功能：比较两个学生成绩，学生a是否排名比学生b更靠前
    96.         if(a[4]4])      //若a比b等级更高
    97.             return true;
    98.         if(a[4]>b[4])      //若a比b等级更低
    99.             return false;
    100.                            //若ab等级相同
    101.         if(a[3]>b[3])      //若总分a>b
    102.             return true;
    103.         if(a[3]3])      //若总分a
    104.             return false;
    105.                            //若ab总分相同
    106.         if(a[1]>b[1])      //若德分a>b
    107.             return true;
    108.         if(a[1]1])      //若德分a
    109.             return false;
    110.                            //若ab德分相等   
    111.         return (a[0]0])?true:false;    //则按考号升序排序
    112.     }
    113. }
    114.  
    115.  
    116.

    解法二 

    考虑到解法一之所以超时，有可能是我自己写的排序算法太慢导致的，于是我就又写了一个算法，利用java自带的Comparator比较器来实现排序。主要思路是，在接收学生信息时只存储不排序，全部接收完毕后，调用java的排序算法，在Arrays.sort()函数中传入一个Comparator匿名内部类（以便自定义排序规则）作为参数，实现排序。最后再降序打印输出。

    这个解法的一个缺点是要对包括未录取考生在内的所有考生进行排序，而解法一只对录取考生排序。（后续的解法我优化了这一点。）解法二的测试结果仍然是有三个测试点超时。代码如下。

    1. /*
    2. 功能：根据规则对给定考生成绩进行排序并输出
    3. 实现思路：用数组存储每个考生的信息，并在Arrays.sort()中传入一个Comparator匿名内部类作为参数，以实现排序。
    4. 时间复杂度   空间复杂度
    5. */
    6. import java.io.*;
    7. import java.util.*;
    8. class Main{
    9.     public static void main(String[] args) throws IOException{
    10.         //接收输入
    11.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    12.         String[] arr1 = br.readLine().split(" +");
    13.         int n = Integer.parseInt(arr1[0]);    //考生总数
    14.         int l = Integer.parseInt(arr1[1]);    //最低录取分数线
    15.         int h = Integer.parseInt(arr1[2]);    //优秀录取线
    16.         //逐个接收考生信息
    17.         Integer[][] a = new Integer[n][5];    //数组每一行代表一个考生，存储考号、德分、才分、总分、等级
    18.         int m = 0;            //录取总人数
    19.         String[] b = new String[3];    //接收当前考生的信息
    20.         for(int i=0;i//在线处理每个考生的信息
    21.             b = br.readLine().split(" +");    //接收当前考生的信息
    22.             for(int j=0;j<3;j++)
    23.                 a[i][j] = Integer.parseInt(b[j]);        //将考生信息转为int    
    24.             a[i] = getGrade2(a[i],l,h);    //调用函数填写总分及等级信息
    25.             if(a[i][4]<5){                //若是第一~第四类考生
    26.                 m++;                        //则录取
    27.             }
    28.         }
    29.         //打印输出
    30.         System.out.print(m);    //输出录取总人数
    31.         if(m==0)    return;        //若是录取人数为0，则直接返回
    32.         //调用java提供的数组排序
    33.         Arrays.sort(a, new Comparator() {    
    34.         		//new一个Comparator匿名内部类，重写compare方法
    35.             public int compare(Integer[] b, Integer[] a) {
    36.               	if(a[4]4])      //若a比b等级更高
    37.                     return 1;
    38.                 if(a[4]>b[4])      //若a比b等级更低
    39.                     return -1;
    40.                                    //若ab等级相同
    41.                 if(a[3]>b[3])      //若总分a>b
    42.                     return 1;
    43.                 if(a[3]3])      //若总分a
    44.                     return -1;
    45.                                    //若ab总分相同
    46.                 if(a[1]>b[1])      //若德分a>b
    47.                     return 1;
    48.                 if(a[1]1])      //若德分a
    49.                     return -1;
    50.                                    //若ab德分相等   
    51.                 return (a[0]0])?1:-1;    //则按考号升序排序
    52.             }
    53.         });
    54.         //降序输出学生信息
    55.         String stu = "";
    56.         for(int i=0;i
    57.             stu = "\n" + a[i][0] + " " +a[i][1] + " " + a[i][2];
    58.             System.out.print(stu);
    59.         }             
    60.     }
    61.     private static Integer[] getGrade2(Integer[] a,int l,int h){
    62.         //功能：根据数组中学生成绩，填写总分及等级信息 。l是录取线，h是优秀线。
    63.         a[3] = a[1] + a[2];    //计算总分
    64.         if(a[1]2]//若德才有一项未达到录取线
    65.             a[4] = 5;        //第五类考生，不予录取
    66.             return a;
    67.         }
    68.         if(a[1]>=h && a[2]>=h){    //若德才均优秀
    69.             a[4] = 1;        //第一类考生
    70.             return a;
    71.         }
    72.         if(a[1]>=h){        //若德分优秀而才分不优秀
    73.             a[4] = 2;        //第二类考生
    74.             return a;
    75.         }    
    76.         if(a[1]>=a[2]){    //若德分不优秀，但德分≥才分
    77.             a[4] = 3;        //第三类考生
    78.             return a;
    79.         }
    80.         a[4] = 4;            //其它考生为第四类考生
    81.         return a;
    82.     }
    83. }

    解法三 

    既然用java自带的排序算法也不行，那索性还是回到解法一的思路，自己用数组做静态链表的排序吧。考虑到解法一中每个考生排序都要从第一类第一名开始比较，比较耗时，因此我又改进了一下，给四个类别分别设置一个本类别第一名的int角标作为指针。这样，每个考生先计算类别并填写在数组中，在排序时只需从所属类别的第一名开始比较即可。此外，这个解法中我还把一些工具函数优化了一下。遗憾的是，测试结果仍然是三个点通过、三个点超时。

    1. /*
    2. 功能：根据规则对给定考生成绩进行排序并输出
    3. 实现思路：用数组存储每个考生的信息，并且用数组作为静态链表实现排序。
    4. 时间复杂度   空间复杂度
    5. */
    6. import java.io.*;
    7. class Main{
    8.     public static void main(String[] args) throws IOException{
    9.         //接收基本信息输入
    10.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    11.         String[] arr1 = br.readLine().split(" +");
    12.         int n = Integer.parseInt(arr1[0]);    //考生总数
    13.         int l = Integer.parseInt(arr1[1]);    //最低录取分数线
    14.         int h = Integer.parseInt(arr1[2]);    //优秀录取线
    15.         //数组初始化
    16.         int[][] a = new int[n][6];    //数组每一行代表一个考生，存储考号、德分、才分、总分、等级、链表序号
    17.         int m = 0;            //录取总人数
    18.         String[] b = new String[3];    //接收当前考生的信息
    19.         Integer yi[] = new Integer[4];  //已录取学生排序链表中第一类至第四类的第一名的角标
    20.         for(int i=0;i<4;i++){           //数组初始化为-1
    21.             yi[i] = -1;
    22.         }
    23.         //在线处理 接收每个学生信息并排序存入数组中
    24.         for(int i=0,temp=-1;i//在线处理每个考生的信息
    25.             b = br.readLine().split(" +");    //接收当前考生的信息
    26.             a[i][0] = Integer.parseInt(b[0]);        //将考生信息转为int
    27.             a[i][1] = Integer.parseInt(b[1]);
    28.             a[i][2] = Integer.parseInt(b[2]);
    29.             a[i] = getGrade(a[i],l,h);    //调用函数填写总分及等级信息，排序地址初始化
    30.             if(a[i][4]!=5){                //若是第一~第四类考生
    31.                 m++;                        //则录取
    32.                 temp =a[i][4]-1;     //当前学生所属类别，从0开始计数，yi[temp]是所属类别第一名的角标
    33.                 a = getSort(a,i,yi[temp]);           //调用函数填写链表地址信息
    34.                 if(a[i][5]==yi[temp])            //判断是否要更新该生所属类别第一名的角标
    35.                     yi[temp] = i;
    36.             }
    37.         }
    38.         //打印输出
    39.         System.out.print(m);    //输出录取总人数
    40.         if(m==0)    return;        //若是录取人数为0，则直接返回
    41.         String stu = "";
    42.         for(int j=0;j<4;j++){       //遍历四个学生类别
    43.             if(yi[j]==-1)               //若当前类别没有学生
    44.                 continue;               //就继续下一个类别
    45.             for(int i=yi[j];;i=a[i][5]){    //按数组静态链表的排序，以成绩降序输出
    46.                 stu = "\n" + a[i][0] + " " +a[i][1] + " " + a[i][2];
    47.                 System.out.print(stu);
    48.                 if(a[i][5]==-1)    //若是链表中录取的最后一名
    49.                     break;            //则跳出循环，停止本类别的打印
    50.             }
    51.         }   
    52.     }
    53.     private static int[] getGrade(int[] a,int l,int h){
    54.         //功能：根据数组中学生成绩，填写总分及等级信息 。l是录取线，h是优秀线。
    55.         if(a[1]2]//若德才有一项未达到录取线
    56.             a[4] = 5;        //第五类考生，不予录取
    57.             return a;
    58.         }
    59.         a[5] = -1;             //对录取学生，排序地址信息初始化
    60.         a[3] = a[1] + a[2];     //对录取学生，计算德才总分
    61.         if(a[1]>=h){    //若德分优秀
    62.             a[4] = (a[2]>=h)?1:2;   //若才分也优秀，则为第一类，否则为第二类
    63.             return a;
    64.         }
    65.         a[4] = (a[1]>=a[2])?3:4;    //若德分不优秀，但德分≥才分，则为第三类，否则其它考生为第四类
    66.         return a;
    67.     }
    68.     private static int[][] getSort(int[][] a,int t,int yi){
    69.         //功能：对数组中指定学生的成绩（以数组静态链表方式）排序并返回数组
    70.         //参数 a[][] 学生信息数组 ；t 待排序学生角标 ；yi 待排序学生所属类别的第一名学生角标
    71.         if(yi==-1)                    //如果当前学生所属类别中还没有学生
    72.             return a;                   //则以待排序学生作为第一名，直接返回
    73.         if(gradeCompare(a[t],a[yi])){        //如果待排序的学生是新的第一名
    74.             a[t][5] = yi;                //待排序学生链接指向原先的第一名
    75.             return a;
    76.         }
    77.         for(int i=yi,j=i;;i=a[i][5]){      //若链表中已经有至少一名学生，则正常进行排序
    78.             if(gradeCompare(a[i],a[t])){    //若待排序学生成绩<当前对比学生成绩
    79.                 j=i;                            //用j记住当前对比学生角标
    80.                 if(a[i][5]==-1){                //若当前对比学生已经是最后一名
    81.                     a[i][5] = t;                    //将待排序学生插入到链表结尾
    82.                     break;                          //排序完毕，退出循环
    83.                 }
    84.             }
    85.             else{                          //若待排序学生成绩>当前对比学生成绩
    86.                 a[j][5] = t;                    //上一名的学生链接到待排序学生（此时j是链表中上一名学生的角标）
    87.                 a[t][5] = i;                    //待排序学生链接到当前对比学生
    88.                 break;                            //排序完毕，退出循环
    89.             }
    90.         }  
    91.         return a;
    92.     }
    93.     private static boolean gradeCompare(int[] a,int[] b){
    94.         //功能：比较两个等级相等的学生成绩，学生a是否排名比学生b更靠前
    95.         if(a[3]!=b[3])        //若总分不相等
    96.             return (a[3]>b[3]);         //则返回总分比较结果
    97.         if(a[1]!=b[1])              //若德分不相等
    98.             return (a[1]>b[1]);         //则返回德分比较结果
    99.         return (a[0]0]);              //最后按考号升序排序
    100.     }
    101. }
    102.  
    103.  
    104.

    解法四 

    我想上边的算法还是太复杂了，计算考生的排名需要计算类别，还要再比较总分、德分、考号，链表的排序也有些麻烦。我想应该可以有更简洁的方式。于是我想到根据考生的类别、总分、德分、考号来生成一个排序的序号（int类型），这个序号越大，考生的排名就应该越靠前。这样，只需要给每个考生计算生成一个序号并填写在数组中，之后在排序时的compare()方法中就只需要比较两个考生的排序序号就可以了。 

    为了能够生成这样一个序号（能体现考生排名的序号），我的思路是，排序时优先看类别，那么类别这一项的优先级就越高，权重就应该越大。以此类推，考号的优先级最低，权重也最小。这个权重，是根据下一级排序项目中两个考生最大的差值计算的，在代码里有注释。这里的总分、德分是按照降序排序的，而类别号则是按照升序排序的。为了统一，我就写了一句“3-zongfen”来把类别号转换成一个降序排序的值。考号有8位，而一个int也就10位（十进制），如果把8位考号全都用上，那就不够用了。题目限定考生数量<10000，大胆猜测考号的前三位是不变的，一直是100 。那么就只截取考号的后五位来参与生成排序序号，前三位就丢掉。

    此外，在这个算法中，代码整体变得更简洁了。从这一点上来说，这是我最满意的一个解法。

    1. /*
    2. 功能：根据规则对给定考生成绩进行排序并输出
    3. 实现思路：用数组存储每个考生的信息，并用考生信息生成唯一序号实现排序。
    4. 时间复杂度   空间复杂度
    5. */
    6. import java.io.*;
    7. import java.util.Arrays;
    8. import java.util.Comparator;
    9. class Main{
    10.     public static void main(String[] args) throws IOException{
    11.         //接收基本信息输入
    12.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    13.         String[] arr1 = br.readLine().split(" +");
    14.         int n = Integer.parseInt(arr1[0]);    //考生总数
    15.         int l = Integer.parseInt(arr1[1]);    //最低录取分数线
    16.         int h = Integer.parseInt(arr1[2]);    //优秀录取线
    17.         //数组初始化
    18.         Integer[][] a = new Integer[n][4];    //数组每一行代表一个考生，存储考号、德分、才分、排序序号
    19.             //注意，因为要用java的Arrays.sort()排序算法，这里要写Integer
    20.         int m = 0;                              //录取总人数
    21.         String[] b = new String[3];           //接收当前考生的String信息
    22.         //在线处理 接收每个学生信息并存入数组中
    23.         for(int i=0;i//在线处理每个考生的信息 i计数当前处理的是第几个考生
    24.             b = br.readLine().split(" +");    //接收当前考生的信息
    25.             for(int j = 0;j<=2;j++)             //将接收的当前考生信息转为int  m表示当前考生存储在考生数组的角标
    26.                 a[m][j] = Integer.parseInt(b[j]);
    27.             if(a[m][1]>=l && a[m][2]>=l){          //如果当前考生为达到录取线的考生 （德分和才分都达到录取线）
    28.                 a[m][3] = getNum(a[m],l,h);       //根据当前考生已有信息，计算生成一个序号，用于排序
    29.                 m++;                             //则录取人数+1  （也就是说，考生数组中当前考生的信息予以保留，不会被覆盖）
    30.             }
    31.         }
    32.         //数组排序
    33.         Arrays.sort(a,0,m,new Comparator() {         //考生数组的0-m角标正是存储的录取学生的信息
    34.             public int compare(Integer[] b, Integer[] a) {  //new一个Comparator匿名内部类，重写compare方法
    35.                 return (a[3]>b[3])?1:-1;                    //通过比较考生的排序序号来进行排序 序号大者排名靠前
    36.             }
    37.         });
    38.         //打印输出
    39.         System.out.print(m);                //输出录取总人数
    40.         if(m!=0)                            //若是录取人数为0，则直接返回 ，若是录取人数不为零，则遍历数组打印考生信息
    41.             for(int i=0;i//输出m个录取考生的信息
    42.                 System.out.print( "\n" + a[i][0] + " " +a[i][1] + " " + a[i][2]);
    43.     }
    44.     private static Integer getNum(Integer[] a,int l,int h){
    45.         //功能：根据考生已有信息，计算生成一个序号，用于排序
    46.         //参数：int[] a 当前考生信息数组；int l最低录取线； int h 优先录取线
    47.  
    48.         //声明变量
    49.         int zongfen=0, dengji = 0, xuhao = 0;       //用于存储当前考生的总分、等级（类别）、排序序号
    50.         //计算并填写当前考生的总分
    51.         zongfen = a[1] + a[2];         //对录取学生，计算德才总分
    52.         //计算并填写当前考生的等级
    53.         if(a[1]>=h)                 //若德分优秀
    54.             dengji = (a[2]>=h)?1:2;       //若才分也优秀，则为第一类，否则为第二类
    55.         else                        //若德分不优秀
    56.             dengji = (a[1]>=a[2])?3:4;    //但德分≥才分，则为第三类，否则其它考生为第四类
    57.         //计算生成用于排序的序号
    58.         xuhao = (3-dengji) * 81 * 41 + zongfen * 41 + a[1];    //取值范围不超过[0,18263]  3-dengji是把等级转化为一个等级越高就越大的值
    59.         xuhao = xuhao * 10000 - (a[0] % 10000);             //把考号后五位也整合在内，生成一个唯一的排序序号  因为考号是升序排列，所以相减
    60.         /*
    61.             采用的方法是给等级、总分、德分、考号赋予不同的权重，由此生成的序号就能体现排序次序。
    62.             能录取的考生AB，德分相差最大是100-60=40，那么就给总分的权重设置为41；
    63.             能录取的考生AB，总分相差最大是200-120=80，那么就给等级设置的权重为81；
    64.             因为考号是8位，比较长，一个int也就10位二进制，因此就单独处理一下，
    65.             已知考生数不超过10000，那么大胆猜测考号前三位是不变的，因此只取考号后五位来生成序号。
    66.         */
    67.         return xuhao;
    68.     }
    69.    
    70. }
    71.  
    72.  
    73.

     结语

    Java解法总结

    以上用java的四种解法都会超时，难道这道题必须用C语言才能不超时吗？题目设置的是不限制语言，这有点不严谨。（后续：我去查看了平台的说明文档，它说，选择合适的编程语言也是能力的一部分，内存和时间限制标准对各个编程语言都设置的是相同的。好吧。）

    为了测试用java解这道题的可行性，我写了一个简单的程序，仅仅读取所有考生信息的输入，而不做任何处理。即便是这样一个显然时间复杂度为线性的程序，测试仍然是三个点超时。也就是说，只要用java，连把所有考生信息都读取一遍都做不到，更别想着排序及打印了。代码如下。

    1. /*
    2. 功能：测试用java是否能在线性复杂度内读取完所有考生信息
    3. 实现思路：只读取每个考生的信息，不做任何处理
    4. 时间复杂度 O(n)   空间复杂度
    5. */
    6. import java.io.*;
    7. class Main{
    8.     public static void main(String[] args) throws IOException{
    9.         //接收基本信息输入
    10.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    //获取输入流对象
    11.         String[] arr1 = br.readLine().split(" +");        //读取基本信息（考生总数、最低录取线、优先录取线）
    12.         int n = Integer.parseInt(arr1[0]);                //将考生总数转为int
    13.         //声明变量
    14.         String[] b = new String[3];           //用于接收当前考生的String信息
    15.         //在线处理 接收每个学生信息并存入数组中
    16.         for(int i=0;i//接收每个考生的信息 i计数当前处理的是第几个考生
    17.             b = br.readLine().split(" +");    //接收当前考生的信息       
    18.     }
    19. }
    20.  
    21.

    C语言代码

    本来打算放弃这道题了。但是又有点不甘心。于是决定把Java程序改写为C语言程序。这部分我借助了AI助手，把上述Java的解法一改写为C语言程序了。所有测试点全部通过！看来我的解法没问题，只是要用C语言而不能用Java。代码如下。

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. typedef struct {
    6.     int id;      // 考号
    7.     int de, cai; // 德分和才分
    8.     int total;   // 总分
    9.     int type;    // 考生类别
    10.     int next;    // 链表中下一个考生的角标
    11. } Student;
    12.  
    13. // 比较函数，用于排序
    14. int compare(const void *a, const void *b) {
    15.     Student *s1 = (Student*)a;
    16.     Student *s2 = (Student*)b;
    17.     if (s1->type != s2->type) {
    18.         return s2->type - s1->type;
    19.     } else if (s1->total != s2->total) {
    20.         return s1->total - s2->total;
    21.     } else if (s1->de != s2->de) {
    22.         return s1->de - s2->de;
    23.     } else {
    24.         return s2->id - s1->id;
    25.     }
    26. }
    27.  
    28. int main() {
    29.     int n, l, h;  // 考生总数，最低录取分数线，优秀录取线
    30.     scanf("%d %d %d", &n, &l, &h);
    31.  
    32.     Student *students = (Student*)malloc(n * sizeof(Student));  // 动态分配内存
    33.  
    34.     int m = 0;  // 录取的学生数
    35.     for (int i = 0; i < n; i++) {
    36.         int id, de, cai;
    37.         scanf("%d %d %d", &id, &de, &cai);
    38.         int total = de + cai;
    39.         if (de >= l && cai >= l) {  // 满足最低录取线
    40.             students[m].id = id;
    41.             students[m].de = de;
    42.             students[m].cai = cai;
    43.             students[m].total = total;
    44.             if (de >= h && cai >= h) {  // 满足优秀录取线
    45.                 students[m].type = 1;  // 第一类考生
    46.             } else if (de >= h && cai < h) {
    47.                 students[m].type = 2;  // 第二类考生
    48.             } else if (de < h && cai < h && de >= cai) {
    49.                 students[m].type = 3;  // 第三类考生
    50.             } else {
    51.                 students[m].type = 4;  // 第四类考生
    52.             }
    53.             students[m].next = -1;  // 初始化为-1，表示没有下一个学生
    54.             m++;
    55.         }
    56.     }
    57.  
    58.     // 按照给定规则排序
    59.     qsort(students, m, sizeof(Student), compare);
    60.  
    61.     // 构建静态链表
    62.     int head = -1;  // 头结点
    63.     for (int i = 0; i < m; i++) {
    64.         if (students[i].type != 5) {  // 只处理可录取的学生
    65.             students[i].next = head;
    66.             head = i;
    67.         }
    68.     }
    69.  
    70.     // 输出结果
    71.     printf("%d", m);
    72.     for (int i = head; i != -1; i = students[i].next) {
    73.         printf("\n%d %d %d", students[i].id, students[i].de, students[i].cai);
    74.     }
    75.  
    76.     free(students);  // 释放内存
    77.  
    78.     return 0;
    79. }

    完毕。

  • 相关阅读:
    leetcode-11. 盛最多水的容器(双指针)
    定时打铃器的单片机控硬件模块
    分布式电源接入对配电网影响分析（Matlab代码实现）
    运行Android Automotive模拟器
    leetcode困难之1127. 用户购买平台
    构建检测，无规矩不成方圆
    CentOS上如何配置手动和定时任务自动进行时间同步
    nginx常用优化
    C++ 语言学习 day10 复习（1）
    Android 9.0 屏蔽设备的定位功能
  • 原文地址：https://blog.csdn.net/Dr_Cheeze/article/details/133563505