【PTA-乙级-详解】1015德才论 超详解 + 排序函数sort()的使用与介绍

【PTA-乙级-详解】1015德才论 超详解 + 排序函数sort()的使用与介绍 前言：

这个题真正让我领会到了库函数的重要性 ：在不知道sort函数之前 我用最基础的算法 写了很久 结果还不对 = = 就很头疼 但是我查其他人的解法中 10个有9个用了sort函数 最开始我不知什么鬼原因 不想用这个sort函数解这个题 最终还是折服了 查了sort()的基本用法后 成功解出了此题

先看 一开始的解法： (错误的，若有人能看出哪里错误，欢迎评论区留言)

#include
using namespace std;
int arr[50000][4];
int main()
{
	int n = 0, min = 0,  max = 0;  
	cin >> n >> min >> max;  //人数 最低  优先
	int num = 0;
	int a1 = 0, a2 = 0, a3 = 0, a4 = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];   //编号 德 才
		if (arr[i][1] < min || arr[i][2] < min)
		{
			arr[i][3] = 0;   //不考虑
			num++;
		}
		if (arr[i][1] >= max && arr[i][2] >= max)
		{
			arr[i][3] = 1;   //德才双全  1
			a1++;
		}
		else if (arr[i][1] >= max && arr[i][2] < max)
		{
			arr[i][3] = 2;   //德到才不到 2
			a2++;
		}
		else if (arr[i][3] != 0 && arr[i][1] < max && arr[i][2] < max && arr[i][1] >= arr[i][2])
		{
			arr[i][3] = 3;   //才德都不行 但是德>=才  3
			a3++;
		}
		else if (arr[i][3] != 0)
		{
			arr[i][3] = 4;   //才德都不行 且德<才  还有  才到德不到 4
			a4++;
		}
	}
	cout << n - num << "n";
	// 排序
	int t = 1;

	int number[5] = { 0,a1,a2,a3,a4 };

	int flag = 1;
	while (1)
	{
		for (int i = 0; i < n; i++)
		{
			// 对某一个进行判断
			if (arr[i][3] == t)
			{
				//  这个是t 让他和除他之外的所有比较
				int tmp = 1;  //标记这个人是否符合输出的条件

				for (int j = 0; j < n; j++)
				{
					if (j != i && arr[j][3] == t)
					{
						// 不对
						//if (arr[j][1] + arr[j][2] >= arr[i][1] + arr[i][2] && arr[j][1] >= arr[i][1] && arr[j][0] < arr[i][0])
						//{
						//	tmp = 0;
						//	break;
						//}
						// 比较
						if (arr[i][1] + arr[i][2] < arr[j][1] + arr[j][2])
						{
							tmp = 0; //有人比他高  tmp=0;
							break;
						}
						if (arr[i][1] + arr[i][2] == arr[j][1] + arr[j][2] && arr[i][1] < arr[j][1])
						{
							tmp = 0; //总分相等 但是有人德比他高
							break;
						}
						if (arr[i][1] + arr[i][2] == arr[j][1] + arr[j][2] && arr[i][1] == arr[j][1] && arr[i][0] > arr[j][0])
						{
							tmp = 0;  //总分 德分都相等 但是有人学号比他小
							break;
						}
					}
				}   
				//break跳出的位置
				if (tmp)
				{
					// tmp=1 满足条件
					printf("%d %d %dn", arr[i][0], arr[i][1], arr[i][2]);
					arr[i][3] = 0;  //把这个输出了的人 置为0  
					number[t]--;
				}
			}
			// 最开始flag是0  
			if (number[1] == 0 && flag == 1)
			{
				t++;
				flag = 2;
			}
			if (number[2] == 0 && flag == 2)
			{
				t++;
				flag = 3;
			}
			if (number[3] == 0 && flag == 3)
			{
				t++;
				flag = 4;
			}
			if (number[4] == 0 && flag == 4)
			{
				return 0;
			}
		}
	}
	return 0;
}

很给我面子  我写了很久的代码  有一个测试点还过了 让我心中万分欣慰（mmp）

 针对此解法的思路：

虽然这个是错的吧 （其实题目中给的那组输入数据在vs中是可以出现正确答案的）但是还是解答一下：运用了二维数组  n行  4列 前三列存放基本信息  第四列存放标号 

输出时  我并没有排序 因为只有一个数组  且排序起来实在太难了 所以也不会排序  然后就硬生生地输出了起来  其实输出过程还是很巧妙的 这里就不详细解答了 有兴趣看上方代码即可

正确的sort解法：

#include
#include
using namespace std;

struct S
{
	int num;
	int morality;
	int ability;
	int sum;
}arr1[100000], arr2[100000], arr3[100000], arr4[100000];

bool cmp(S a, S b)
{
	if (a.sum != b.sum)
		return a.sum > b.sum;
	if (a.sum == b.sum && a.morality != b.morality)
		return a.morality > b.morality;
	if (a.sum == b.sum && a.morality == b.morality)
		return a.num < b.num;
}

int main()
{
	int n, min, max;
	cin >> n >> min >> max;
	
	int a = 0, d = 0, c = 0;   //学号 德 才
	int number = 0;
	int n1 = 0, n2 = 0, n3 = 0, n4 = 0;
	while (number < n)
	{
		cin >> a >> d >> c;
		if (d >= min && c >= min)
		{
			// 予以考虑的人
			if (d >= max && c >= max)
			{
				arr1[n1].num = a;
				arr1[n1].morality = d;
				arr1[n1].ability = c;
				arr1[n1].sum = d + c;
				n1++;
			}
			else if (d >= max && c < max)
			{
				arr2[n2].num = a;
				arr2[n2].morality = d;
				arr2[n2].ability = c;
				arr2[n2].sum = d + c;
				n2++;
			}
			else if (d < max && c < max && d >= c)
			{
				arr3[n3].num = a;
				arr3[n3].morality = d;
				arr3[n3].ability = c;
				arr3[n3].sum = d + c;
				n3++;
			}
			else
			{
				arr4[n4].num = a;
				arr4[n4].morality = d;
				arr4[n4].ability = c;
				arr4[n4].sum = d + c;
				n4++;
			}
		}
		number++;
	}
	cout << n1 + n2 + n3 + n4 << endl;
	sort(arr1, arr1 + n1, cmp);
	sort(arr2, arr2 + n2, cmp);
	sort(arr3, arr3 + n3, cmp);
	sort(arr4, arr4 + n4, cmp);
	for (int i = 0; i < n1; i++)
	{
		printf("%d %d %dn", arr1[i].num, arr1[i].morality, arr1[i].ability);
	}
	for (int i = 0; i < n2; i++)
	{
		printf("%d %d %dn", arr2[i].num, arr2[i].morality, arr2[i].ability);
	}
	for (int i = 0; i < n3; i++)
	{
		printf("%d %d %dn", arr3[i].num, arr3[i].morality, arr3[i].ability);
	}
	for (int i = 0; i < n4; i++)
	{
		printf("%d %d %dn", arr4[i].num, arr4[i].morality, arr4[i].ability);
	}
	return 0;
}

说真的 我认为这段代码比较起来看上去还是很干净整洁的  // 手动狗头

分析：

1.  建立结构体  以表示一个人 存放一个人的信息 

2.  将四个阶层的人放在四个结构体数组中 然后对每一个数组用强大的sort函数进行排序 

3.  排序好之后输出即可

容易错的点：

cmp函数的第二个if中  一开始我没有写  && a.morality != b.morality 然后就错了  其实这个是很有必要的 因为当两个人总分一样时  只有德分不同才输出  = = 有关这个return 我也是第一次用sort  所以给不出太多详细解释

别的就没什么了  关于人的分类中 只要认真读题  仔细想一下就ok了 

补充：

（这个题的大致解法都差不多  但是也有很多点可以用不同的方法实现 ） ：

可以只建立一个结构体数组 同时在结构体中多加一个存储阶层的变量  在sort函数中cmp函数实现时 多加一个判断  

还可以对比较符 “ <  ”和 “ > ” 进行重载   让他们可以用来对结构体变量进行比较  这样cmp函数中就可以写的更简洁一些

可以对数组赋值 数组打印 这些功能放在函数中 这样模块化会更明显一些 

总结：

库函数很重要！！！ 后续很有心思专门对sort函数写一篇文章介绍使用语法和使用方式  以及对一些常用函数的补充的文章  值得期待= = ；