PAT-B1032-挖掘机技术哪家强

题目（20分）

为了用事实说明挖掘机技术到底哪家强，PAT 组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入

输入在第 1 行给出不超过 10**5 的正整数 N，即参赛人数。随后 N 行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从 1 开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。

6
3 65
2 80
1 100
2 70
3 40
3 0

输出

在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

2 150

我的做法

1. 定义一个结构体，将编号和成绩作为一个结构体的数据；
2. 使用scanf将每个数据（即学生的学校编号和成绩）录入结构体数组；
3. 对数组进行遍历操作，相同编号的，成绩相加，只保留第一次遇到的编号数据，剩余的编号置零，结束后会得到类似于去重一样的效果；
4. 遍历一次数组，选出编号不为0的且成绩总分最高的，输出即可。

#include<stdio.h>struct stuInfo{                     //定义学生成绩结构体int index;                      //编号int mark;                       //成绩stuInfo(){}                     //无参数构造方法stuInfo(int _index,int _mark){  //自定义构造方法index=_index;mark=_mark;}
};int main(){/*录入数据*/int t;              //循环次数，即学生个数scanf("%d",&t);     int stuLen=t;       //保存个副本，后面用stuInfo stu[t];     //初始化一个保存学生结构的数组stu   while(t--){		    //挨个录入数据 int a,b;scanf("%d %d",&a,&b);stu[t]=stuInfo(a,b);}/*进行合并，计算总分*/for(int i=0;i<stuLen;i++){      if(stu[i].index==0){                //若编号为0，则直接结束本次循环continue;} for(int j=i+1;j<stuLen;j++){if(stu[i].index==stu[j].index){stu[i].mark+=stu[j].mark;       //如果编号一样，就将成绩加到前一个数组元素上stu[j].index=0;	                //将被合并的编号置0} }  }/*遍历比较大小*/int max=0,num=0;for(int k=0;k<stuLen;k++){if(stu[k].index==0){    //编号为0，就跳过本次循环continue;} if(stu[k].mark>max){	max=stu[k].mark;num=stu[k].index;}}/*输出数据*/printf("%d %d",num,max);return 0;
}

分数结果

20分得到15分，一个答案错误，一个运行超时。虽然觉得有优化的空间，但不知道在哪里优化。

看答案修改后AC成功

#include<stdio.h>struct stuInfo{                     //定义学生成绩结构体int index;                      //编号int mark;                       //成绩stuInfo(){}                     //无参数构造方法stuInfo(int _index,int _mark){  //自定义构造方法index=_index;mark=_mark;}
};int main(){/*录入数据*/int t;              //循环次数，即学生个数scanf("%d",&t);     stuInfo stu[t];     //初始化一个保存学生结构的数组stufor(int i=0;i<t;i++){int a,b;scanf("%d %d",&a,&b);stu[i]=stuInfo(a,b);}/*数组求和*/int amout[100000]={0};  //初始化一个数组，存储成绩for(int i=0;i<t;i++)amout[stu[i].index]+=stu[i].mark;//编号对应下标。因学校编号是从1开始连续的，所以可以这么做/*遍历比较大小*/   int max=-1,num=1;           //学校编号最少都是1,故初值只能为1for(int i=1;i<=t;i++){      //学校编号是从1开始的，故i初值为1if(max<amout[i]){max=amout[i];num=i;}}/*输出*/printf("%d %d\n",num, max);return 0;
}

总结

1. 本题答案是直接用数组的，无论是代码量还是复杂度都比我的简单很多。
2. 但是我认为我起初的解题思路也是正确的，在起初代码的第39行，将num的初值修改为1后，拿到了17分，因为运行超时被扣3分。
3. 参考答案的解法后，错误原因在于未重视学校编号是从1开始连续递增这一条件。

两相对比

1. 我的方法略显拙劣，for循环的嵌套也让时间复杂度上了一个台阶，但优点在于可以节约大约2/3的空间以及具有更好的普适性，可以接受学校编号不连续的情况，且使用结构体，也使得程序可读性变高，缺点容易超时。
2. 答案的方法，仅使用了数组，时间上有优势，代码简洁，但空间上利用率不高，我不喜欢。