[C++知识库]C语言PAT刷题 - 1015 德才论

作者的话：若有朋友复制代码去PAT试着运行遇到问题的：
1.可能是格式问题，可以先把从本站复制的代码粘贴到记事本，再把记事本里的代码复制，然后粘贴到PAT的代码区，提交本题回答，应该就可以了；
2.可能是注释原因，PAT有时候检测到注释会编译错误，所以可以先把注释删了，再进行提交回答。
3.可能是作者当初根据题目写出来的代码仍存在一些疏漏，而恰好当时的测试机制没那么完善，没检测出问题。后面测试机制有所更新，故出现问题，若有相关需要的可以评论区留言或私信作者，我看到的话会去再查一下疏漏之处，然后更新文章。

一、题目描述
宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”：“是故才德全尽谓之圣人，才德兼亡谓之愚人，德胜才谓之君子，才胜德谓之小人。凡取人之术，苟不得圣人，君子而与之，与其得小人，不若得愚人。”
现给出一批考生的德才分数，请根据司马光的理论给出录取排名。
输入格式：
输入第一行给出 3 个正整数，分别为：N（≤10⁵），即考生总数；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

二、解题思路
读题：
德才有四种境界：1.圣人(德才兼备) 2.君子(德>才) 3.愚人(德才兼亡) 4.小人(才>德)
我们先接收三个正整数N(考生人数)、L(最低录取线)、H(优先录取线)，得到招生标准，然后接收N个考生的考号、德分、才分。按招生标准进行检测，没到最低分数线L的直接淘汰，到最低录取线的同学对他们进行分类，第一类是德才兼备的圣人(德分和才分都达到优先录取线的人)；第二类是德胜才的君子(只有德分过线的人)；第三类是愚人(都没过线但德分不低于才分的人)；第四类是小人(没有全部到达优先录取线且才分大于德分的人)。
最后分出四大类学生，每一类学生内部按总分从高到低排序(当总分相同时，德分高者优先；德分相同时，按考号升序输出)，且排列顺序上第一类>第二类>第三类>第四类。
经过检测后，程序要先输出到达最低录取线的人数M，并在之后M行，按排列顺序每行输出一位考生的相关信息。
思路：
（1）原始思路(存在问题，最后运行超时)
1.由于考生信息包含考号、德分、才分，三者相互关联，且每个信息还需要用到总分、分类序号两个成员属性，为维持这种关联性，可以创建结构体类型Stu；
2.定义需要的变量(实际解题时是先定义认为需要用到的变量，后面遇到问题需要新定义变量时再回到上头来定义新的变量)，从键盘接收正整数N、L、H存放在变量n、l、h中；
3.循环接收n个学生信息，过底线的保存到数组里，没过的学生信息丢了（以免后面分类时造成干扰）。此时数组中存储了所有及格的学生信息——考号，德分，才分，循环变量i正好是过最低录取线的学生的人数，将其输出，根据i是否为0决定是否换行；
4.遍历数组，根据学生生信息对学生进行分类，顺便算一下合格每位学生的总分并存入score；
5.使用冒泡排序，根据类号、总分、德分、考号对学生信息排序；
6.设置循环输出学生信息。

（2）查攻略重生后的船新版本
这道题折磨了我两天时间，本来冒泡排序就用的不是很顺手，这道题直接给我来一波大的——冒泡排序悲催的超时了。最后只能用库函数qsort进行快速排序，从而避免超时。qsort还是蛮好的，可惜我当初学过后就丢掉了，看到这道题压根没想到这神器，自己写了一天还是白搭，最后找网上大神版本借鉴才终于解决了超时问题。如果大家有其它解题方法也欢迎分享，我的眼界太窄了，需要大佬给我开开眼。

船新版本的思路和原来差不了多少，主要就是第五点的排序不再使用冒泡排序，而是使用库函数qsort，使用qsort又需要引用头文件<stdlib.h>和新定义一个函数cmp来确定排序规则，其他的一切如旧。
三、具体实现
0.标准C源程序框架

#include <stdio.h>
int main()
{
	return 0;
}

1.由于考生信息包含考号、德分、才分，三者相互关联，且每个信息还需要用到总分、分类序号两个成员属性，为维持这种关联性，可以创建结构体类型Stu；

typedef struct Stu
{
	int no; //考号
	int d;  //德分
	int c;  //才分
	int score;     //总分
	int result;    //学生大类序号
}Stu;

2.定义需要的变量(实际解题时是先定义认为需要用到的变量，后面遇到问题需要新定义变量时再回到上头来定义新的变量)，从键盘接收正整数N、L、H存放在变量n、l、h中；

	int n, l, h;
	int i = 0;
	int j = 0;//冒泡排序内层循环的循环变量
	int temp = 0;//临时变量
	Stu s[100000];//结构体Stu型数组
	scanf("%d%d%d", &n, &l, &h);

3.循环接收n个学生信息，过底线的保存到数组里，没过的学生信息丢了（以免后面分类时造成干扰）。此时数组中存储了所有及格的学生信息——考号，德分，才分，循环变量i正好是过最低录取线的学生的人数，将其输出，根据i是否为0决定是否换行；

	do {
		scanf("%d%d%d", &s[i].no, &s[i].d, &s[i].c);
		if ((s[i].d >= l) && (s[i].c >= l))//只有都过底线时,学生信息才会保存，不然会被后面学生的信息覆盖
		{
			i++;
		}
	} while (--n);
	n = i;//保留下来的学生有i个（若最后一个学生没过底线，他的信息依然在数组里，但是没有被算在过线总人数里）
	printf("%d", i);//输出几个学生留了下来
	if (i != 0)    printf("\n"); //当i=0时说明今年招生全军覆没，后面不需要再输出学生信息，自然也不用换行

4.遍历数组，根据学生生信息对学生进行分类，顺便算一下合格每位学生的总分并存入score；

	for (i = 0; i < n; i++)
	{
		if ((s[i].c >= h) && (s[i].d >= h))            s[i].result = 1;
		else if (s[i].d >= h)                          s[i].result = 2;
		else if ((s[i].c < h) && (s[i].c <= s[i].d))   s[i].result = 3;
		else                                           s[i].result = 4;
		s[i].score = s[i].d + s[i].c;
	}

5.使用冒泡排序，根据类号、总分、德分、考号对学生信息排序；

	for (i = 0; i < n - 1; i++)
	{
		int flag = 1;//假设这一趟要排序的数据已经有序
		//每一趟冒泡排序
		for (j = 0; j < n - 1 - i; j++)
		{
			if ((s[j].result > s[j + 1].result)//类号从小到大
				|| ((s[j].result == s[j + 1].result) && (s[j].score < s[j + 1].score))//总分降序
				|| ((s[j].result == s[j + 1].result) && (s[j].score == s[j + 1].score) && (s[j].d < s[j + 1].d))//德分降序
				|| ((s[j].result == s[j + 1].result) && (s[j].score == s[j + 1].score) && (s[j].d == s[j + 1].d) && (s[j].no > s[j + 1].no)))//考号升序
			{
				temp = s[j].no;
				s[j].no = s[j + 1].no;
				s[j + 1].no = temp;//1.考号交换
				temp = s[j].d;
				s[j].d = s[j + 1].d;
				s[j + 1].d = temp;//2.德分交换
				temp = s[j].c;
				s[j].c = s[j + 1].c;
				s[j + 1].c = temp;//3.才分交换
				temp = s[j].score;
				s[j].score = s[j + 1].score;
				s[j + 1].score = temp;//4.总分交换
				temp = s[j].result;
				s[j].result = s[j + 1].result;
				s[j + 1].result = temp;//5.类号交换
				flag = 0;//本趟排序的数据其实不完全有序
			}
		}
		if (flag == 1)//数组全部元素都正确归位了，结束排序(循环)
		{
			break;
		}
	}

6.设置循环输出学生信息。

	for (i = 0; i < n; i++)
	{
		printf("%d %d %d", s[i].no, s[i].d, s[i].c);
		if (i < (n - 1))
		{
			printf("\n");
		}
	}

（2）查攻略重生后的船新版本
5.定义比较函数，调用库函数qsort()；

//定义比较函数
int cmp(const void* a, const void* b)
{
	Stu* pa = (Stu*)a;
	Stu* pb = (Stu*)b;
	if (pa->result < pb->result)//如果大类序号小的在前面，就不用交换次序
	{
		return -1;
	}
	else if ((pa->result == pb->result) && (pa->score > pb->score))//如果同类，总分高的在前面，就不用交换次序
	{
		return -1;
	}
	else if ((pa->result == pb->result) && (pa->score == pb->score) && (pa->d > pb->d))//同类同分，德分高的在前面就不用交换
	{
		return -1;
	}
	else if ((pa->result == pb->result) && (pa->score == pb->score) && (pa->d == pb->d) && (pa->no < pb->no))//同类同分同德分，考号小的在前面就不用交换
	{
		return -1;
	}
	else
	{
		return 1;
	}
}

//调用库函数qsort()
//根据类号、总分、德分、考号对学生信息排序
qsort(s, n, sizeof(Stu), cmp);

四、测试数据
1.题目给的输入输出用例
2.

   输入：
   2 60 80
   1 10 20
   2 10 20
   （这个测试数据是看你的程序在遇到全军覆没情况时是否还会错误输出学生信息，至于我怎么发现的？自然是我犯了这个错误(哭)）
   输出：
   0

五、全部代码
（1）原始思路(存在问题，最后运行超时，大家可以试着改进，若能改进出成功版本，欢迎分享)

#include <stdio.h>
/*目标：先接收n(学生数量), l(底线), h(优秀线)，然后接收n个学生信息，对过底线的学生进行分类与排序，然后按顺序输出
分类规则：1.两门课都过高分线 2.只有D课过高分线 3.都没过线，但D>C 4.else
处理过程：
1.scanf接收n,l,h;
2.循环接收n个学生信息，过底线的保存到数组里，没过的学生信息丢了（以免后面分类时造成干扰）；
此时数组中存储了所有及格的学生信息——考号，c，d
3.分类：for循环遍历数组，双高者result=1;else if(d>=h) result=2；else if(c<h&&c<=d)result=3；else result=4
*/
typedef struct Stu
{
	int no; //考号
	int d;  //德分
	int c;  //才分
	int score;     //总分
	int result;    //学生大类序号
}Stu;
int main()
{
	int n, l, h;
	int i = 0;
	int j = 0;//冒泡排序内层循环的循环变量
	int temp = 0;//临时变量
	Stu s[100000];//结构体Stu型数组
	scanf("%d%d%d", &n, &l, &h);
	do {
		scanf("%d%d%d", &s[i].no, &s[i].d, &s[i].c);
		if ((s[i].d >= l) && (s[i].c >= l))//只有都过底线时,学生信息才会保存，不然会被后面学生的信息覆盖
		{
			i++;
		}
	} while (--n);
	n = i;//保留下来的学生有i个（若最后一个学生没过底线，他的信息依然在数组里，但是没有被算在过线总人数里）
	printf("%d", i);//输出几个学生留了下来
	if (i != 0)    printf("\n"); //当i=0时说明今年招生全军覆没，后面不需要再输出学生信息，自然也不用换行
	//对学生进行分类
	for (i = 0; i < n; i++)
	{
		if ((s[i].c >= h) && (s[i].d >= h))            s[i].result = 1;
		else if (s[i].d >= h)                          s[i].result = 2;
		else if ((s[i].c < h) && (s[i].c <= s[i].d))   s[i].result = 3;
		else                                           s[i].result = 4;
		s[i].score = s[i].d + s[i].c;
	}
	//根据类号、总分、德分、考号对学生信息排序
	for (i = 0; i < n - 1; i++)
	{
		int flag = 1;//假设这一趟要排序的数据已经有序
		//每一趟冒泡排序
		for (j = 0; j < n - 1 - i; j++)
		{
			if ((s[j].result > s[j + 1].result)//类号从小到大
				|| ((s[j].result == s[j + 1].result) && (s[j].score < s[j + 1].score))//总分降序
				|| ((s[j].result == s[j + 1].result) && (s[j].score == s[j + 1].score) && (s[j].d < s[j + 1].d))//德分降序
				|| ((s[j].result == s[j + 1].result) && (s[j].score == s[j + 1].score) && (s[j].d == s[j + 1].d) && (s[j].no > s[j + 1].no)))//考号升序
			{
				temp = s[j].no;
				s[j].no = s[j + 1].no;
				s[j + 1].no = temp;//1.考号交换
				temp = s[j].d;
				s[j].d = s[j + 1].d;
				s[j + 1].d = temp;//2.德分交换
				temp = s[j].c;
				s[j].c = s[j + 1].c;
				s[j + 1].c = temp;//3.才分交换
				temp = s[j].score;
				s[j].score = s[j + 1].score;
				s[j + 1].score = temp;//4.总分交换
				temp = s[j].result;
				s[j].result = s[j + 1].result;
				s[j + 1].result = temp;//5.类号交换
				flag = 0;//本趟排序的数据其实不完全有序
			}
		}
		if (flag == 1)//数组全部元素都正确归位了，结束排序(循环)
		{
			break;
		}
	}
	for (i = 0; i < n; i++)
	{
		printf("%d %d %d", s[i].no, s[i].d, s[i].c);
		if (i < (n - 1))
		{
			printf("\n");
		}
	}
}

（2）查攻略重生后的船新版本

#include <stdio.h>
#include <stdlib.h>
typedef struct Stu
{
	int no; //考号
	int d;  //德分
	int c;  //才分
	int score;     //总分
	int result;    //学生大类序号
}Stu;
int cmp(const void* a, const void* b)
{
	Stu* pa = (Stu*)a;
	Stu* pb = (Stu*)b;
	if (pa->result < pb->result)//如果大类序号小的在前面，就不用交换次序
	{
		return -1;
	}
	else if ((pa->result == pb->result) && (pa->score > pb->score))//如果同类，总分高的在前面，就不用交换次序
	{
		return -1;
	}
	else if ((pa->result == pb->result) && (pa->score == pb->score) && (pa->d > pb->d))//同类同分，德分高的在前面就不用交换
	{
		return -1;
	}
	else if ((pa->result == pb->result) && (pa->score == pb->score) && (pa->d == pb->d) && (pa->no < pb->no))//同类同分同德分，考号小的在前面就不用交换
	{
		return -1;
	}
	else
	{
		return 1;
	}
}
int main()
{
	int n, l, h;
	int i = 0;
	int j = 0;//冒泡排序内层循环的循环变量
	int temp = 0;//临时变量
	Stu s[100000];//结构体Stu型数组
	scanf("%d%d%d", &n, &l, &h);
	do {
		scanf("%d%d%d", &s[i].no, &s[i].d, &s[i].c);
		if ((s[i].d >= l) && (s[i].c >= l))//只有都过底线时,学生信息才会保存，不然会被后面学生的信息覆盖
		{
			i++;
		}
	} while (--n);
	n = i;//保留下来的学生有i个（若最后一个学生没过底线，他的信息依然在数组里，但是没有被算在过线总人数里）
	printf("%d", i);//输出几个学生留了下来
	if (i != 0)    printf("\n"); //当i=0时说明今年招生全军覆没，后面不需要再输出学生信息，自然也不用换行
	//对学生进行分类
	for (i = 0; i < n; i++)
	{
		if ((s[i].c >= h) && (s[i].d >= h))            s[i].result = 1;
		else if (s[i].d >= h)                          s[i].result = 2;
		else if ((s[i].c < h) && (s[i].c <= s[i].d))   s[i].result = 3;
		else                                           s[i].result = 4;
		s[i].score = s[i].d + s[i].c;
	}
	//根据类号、总分、德分、考号对学生信息排序
	qsort(s, n, sizeof(Stu), cmp);
	//按顺序输出学生信息
	for (i = 0; i < n; i++)
	{
		printf("%d %d %d", s[i].no, s[i].d, s[i].c);
		if (i < (n - 1))
		{
			printf("\n");
		}
	}
}