输入格式：
输入第一行给出 3 个正整数，分别为：N（≤105），即考生总数；L（≥60），为录取最低分数线，即德分和才分均不低于 L 的考生才有资格被考虑录取；H（<100），为优先录取线——德分和才分均不低于此线的被定义为“才德全尽”，此类考生按德才总分从高到低排序；才分不到但德分到线的一类考生属于“德胜才”，也按总分排序，但排在第一类考生之后；德才分均低于 H，但是德分不低于才分的考生属于“才德兼亡”但尚有“德胜才”者，按总分排序，但排在第二类考生之后；其他达到最低线 L 的考生也按总分排序，但排在第三类考生之后。
随后 N 行，每行给出一位考生的信息，包括：准考证号 德分 才分，其中准考证号为 8 位整数，德才分为区间 [0, 100] 内的整数。数字间以空格分隔。
输出格式：
输出第一行首先给出达到最低分数线的考生人数 M，随后 M 行，每行按照输入格式输出一位考生的信息，考生按输入中说明的规则从高到低排序。当某类考生中有多人总分相同时，按其德分降序排列；若德分也并列，则按准考证号的升序输出。
输入样例：
14 60 80
10000001 64 90
10000002 90 60
10000011 85 80
10000003 85 80
10000004 80 85
10000005 82 77
10000006 83 76
10000007 90 78
10000008 75 79
10000009 59 90
10000010 88 45
10000012 80 100
10000013 90 99
10000014 66 60
输出样例：
12
10000013 90 99
10000012 80 100
10000003 85 80
10000011 85 80
10000004 80 85
10000007 90 78
10000006 83 76
10000005 82 77
10000002 90 60
10000014 66 60
10000008 75 79
10000001 64 90 需要注意的地方：
本题不算是一道难题，仔细读题之后会发现就是根据成绩及学号将学生分类排序。思路很清晰，定义一个学生类类（或结构体），然后根据题目描述的一步一步的来进行分类，用常规方法很容易能够输出想要的结果，但是你提交时你会发现会超时。题目中所给的数据范围时10000，如果你的排序算法的时间复杂度为O(n*n)，那一定会超时。因此这里的排序算法就非常重要，而之前我提交时用的排序算法是冒泡，时间复杂度为O(n*n)，我提交之后有俩测试用例超时，因此我选择了c库函数stdlib.h中的qsort函数。qsort函数的时间复杂度接近O(nlogn)，这时候问题成功解决。下面给出qsort()函数用法：具体用法见这里
void qsort(void *arr, n, size, int (*compar)(const void *, const void*))
- arr -- 指向要排序的数组的第一个元素的指针。
- n -- 由 arr指向的数组中元素的个数。
- size -- 数组中每个元素的大小，以字节为单位。结构体或对象用sizeof()。
- compar -- 用来比较两个元素的函数
AC代码:
#include<iostream>
#include<cstdlib>
using namespace std;
class Student{
private:
long int studentId;
int de_grade;
int cai_grade;
public:
long int getStudentId()
{
return this->studentId;
}
void setStudentId(long int sId)
{
this->studentId = sId;
}
int getDe_grade()
{
return this->de_grade;
}
void setDe_grade(int de_grade)
{
this->de_grade = de_grade;
}
int getCai_grade()
{
return this->cai_grade;
}
void setCai_grade(int cai_grade)
{
this->cai_grade =cai_grade;
}
Student(long int sId,int de_grade,int cai_grade)
{
this->studentId=sId;
this->de_grade = de_grade;
this->cai_grade = cai_grade;
}
int getGrades()
{
return this->cai_grade+this->de_grade;
}
Student(){}
Student &operator =(Student &s1)
{
this->de_grade = s1.de_grade;
this->cai_grade = s1.cai_grade;
this->studentId = s1.studentId;
return *this;
}
};
int com(const void *a,const void *b)
{
Student *s1,*s2;
s1 = (Student *)a;
s2 = (Student *)b;
if(s1->getGrades()!=s2->getGrades())//以总分降序排序
{
return s2->getGrades()>s1->getGrades();
}
else if(s1->getDe_grade()!=s2->getDe_grade())//以德分降序
{
return s2->getDe_grade()>s1->getDe_grade();
}
else if(s1->getStudentId()!=s2->getStudentId())//按学号升序排序
{
return s1->getStudentId()>s2->getStudentId();
}
}
void printfResult(Student s[],int n)//输出
{
for(int i=0;i<n;i++)
{
Student stu=s[i];
printf("%d %d %d\n",stu.getStudentId(),stu.getDe_grade(),stu.getCai_grade());
}
}
void classifybyGrade(int n,int L,int H,Student student[])
{
Student student_1[n];//才德全尽的学生
Student student_2[n];//德胜才的学生
Student student_3[n];//德才得兼亡，但德胜才的学生
Student student_4[n];//其他到L线的学生
Student temp;
int de_grade, cai_grade,j=0,k=0,l=0,m=0;
for(int i=0;i<n;i++)
{
de_grade = student[i].getDe_grade();
cai_grade = student[i].getCai_grade();
if(de_grade>=L&&cai_grade>=L)//过线学生
{
if(de_grade>=H&&cai_grade>=H) // 才德全尽的学生
{
student_1[m++] = student[i];
}else if(cai_grade<H&&de_grade>=H)//德胜才的学生
{
student_2[j++] = student[i];
}else if(cai_grade<H&&de_grade<H&&de_grade>=cai_grade)//德才得兼亡，但德胜才的学生
{
student_3[k++] = student[i];
}else{//其他到L线的学生
student_4[l++] = student[i];
}
}
}
cout<<m+j+k+l<<endl;
//排序
qsort(student_1,m,sizeof(temp),com);
qsort(student_2,j,sizeof(temp),com);
qsort(student_3,k,sizeof(temp),com);
qsort(student_4,l,sizeof(temp),com);
//输出
printfResult(student_1,m);
printfResult(student_2,j);
printfResult(student_3,k);
printfResult(student_4,l);
return;
}
int main()
{
int N,L,H;
scanf("%d %d %d",&N,&L,&H);
long int sId;
int d;
int c;
Student stu[100010];
for(int i=0;i<N;i++)
{
scanf("%ld %d %d",&sId,&d,&c);
stu[i].setStudentId(sId);
stu[i].setDe_grade(d);
stu[i].setCai_grade(c);
}
classifybyGrade(N,L,H,stu);
return 0;
}
京公网安备 11010502036488号