正经题解｜优才选拔

题目大意

题目共会给出$n$位学生的信息，信息为:姓名、德分、才分。要求你根据给出的德分与才分划分学生的名次。

题意分析

题目描述当中，给出了学生名词排序的优先级顺序，顺序如下

1、 按照德分排序，德分较高者排名靠前。

2、 按照才分排序，才分较高者排名靠前。

3、 如果分数皆相等，最后按照名字的字典序顺序，较小者靠前。

最后根据排名，从上至下输出排名对应的学生姓名即可，需要注意，只有德才分均为60及以上的同学才可输出，每个名字独占一行。

解题思路

本题根据给出的描述，我们可以得知需要按照优先级进行排序，那么我们就可以联想到结构体排序。

根据优先级我们可以编写出一段比较函数的伪代码，其中f与k分别代表德分与才分。

if a.f != b.f 
    return a.f > b.f
else if a.k != b.k
    return a.k > b.k
else 
    return a.name < b.name 

最后只需要在输出的时候根据分数是否都在60分及以上输出名字即可。

时间复杂度解析

需要使用到结构体排序，共有n个元素，所以最后的时间复杂度为$O(nlogn)$

代码演示

#include<bits/stdc++.h> 
using namespace std;
struct Node{
	string name;
	int f,k;
}a[100005];
bool cmp(Node a,Node b)
{
	if(a.f!=b.f)return a.f > b.f;
	if(a.k!=b.k)return a.k > b.k;
	return a.name < b.name;
}
int main()
{
	int n;
	cin >> n;
	for(int i = 1 ; i <= n ; i ++ )
	{
		cin >> a[i].name >> a[i].f >> a[i].k ;
	}
	sort(a+1,a+1+n,cmp);
	for(int i = 1 ; i <= n ; i ++ )
	{
		if(a[i].f >= 60 && a[i].k >= 60)cout << a[i].name << endl;
	}
	return 0;
}