题目链接：1015 德才论

上篇链接：【PAT乙】1015 德才论 ——上篇（链表练习)（运行超时）

思路

今天的任务主要就是补坑，做过的题目都AC了治愈了多年的强迫症～

这道题自我感觉写得还可以，收获了一些用C++时候得注意事项。

重点收获：用了sort后依然超时，看了几遍也找不到可优化的地方，最后突然灵光一闪看见了cin，想起来cin比scanf耗时长，顺手也把cout改成了printf，有一个190+ms的测试点直接变成了55ms，差了将近4倍的时间，对以后解决超时问题有了新的理解。代码过程： 结构体存储学生数据，其中条目增加总分用于排序，输入每条数据时即进行判断分类，加入相应类别学生数组中。编写cmp使用sort对每个类别按照先总分，再德分由高到低，再学号由低到高的顺序排序，sort内部使用了快排，O（nlog2n）的时间复杂度有利于解决超时问题。最终按照要求依序输出即可。

代码

#include<iostream> #include<algorithm> using namespace std; struct Student{//学生类 int no,dem,sci;//准考证,德分,才分 int sum;//总分 }stu[4][100000]; int cmp(Student a, Student b){ if(a.sum == b.sum){ if(a.dem == b.dem) return a.no < b.no; return a.dem > b.dem; } return a.sum > b.sum; } int main(){ int N,L,H,no,dem,sci,sel; int a[4] = {0};//四类考生数量初始为0 scanf("%d %d %d",&N,&L,&H); for(int i=0;i<N;i++){ scanf("%d %d %d",&no,&dem,&sci); if(dem >= L && sci >= L){//不合格则直接跳过 sel = 3;//默认置为第四类，按照以下条件再改 if(dem >= H && sci >= H) sel=0; else if(dem >= H) sel =1; else if(dem >= sci) sel = 2; stu[sel][a[sel]].no = no; stu[sel][a[sel]].dem = dem; stu[sel][a[sel]].sci = sci; stu[sel][a[sel]++].sum = dem + sci; } } cout << a[0] + a[1] + a[2] + a[3] << endl; for(int i=0;i<4;i++){ sort(stu[i],stu[i] + a[i],cmp); for(int j=0;j<a[i];j++){ printf("%d %d %d\n",stu[i][j].no,stu[i][j].dem,stu[i][j].sci); } } return 0; }