PAT A1036 Boys vs Girls

前言

正文

题目描述

This time you are asked to tell the difference between the lowest grade of all the male students and the highest grade of all the female students.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N, followed by N lines of student information. Each line contains a student’s name, gender, ID and grade, separated by a space, where name and ID are strings of no more than 10 characters with no space, gender is either F (female) or M (male), and grade is an integer between 0 and 100. It is guaranteed that all the grades are distinct.

Output Specification:

For each test case, output in 3 lines. The first line gives the name and ID of the female student with the highest grade, and the second line gives that of the male student with the lowest grade. The third line gives the difference grade_F −grade_M
. If one such kind of student is missing, output Absent in the corresponding line, and output NA in the third line instead.

Sample Input 1:

3
Joe M Math990112 89
Mike M CS991301 100
Mary F EE990830 95

Sample Output 1:

Mary EE990830
Joe Math990112
6

Sample Input 2:

1
Jean M AA980920 60

Sample Output 2:

Absent
Jean AA980920
NA

解题思路:

这里提供两种解题思路，两种方法都需要构造结构体，只是结构体中的数据项不同，第一种方法容易想到，但时间复杂度更高，因此更推荐第二种方法

法一:
直接将所有数据读入到结构体数组，再利用STL的sort进行排序，然后遍历，找到分数最高的女生以及分数最低的男生，再经过简单的判断，按照题目要求输出即可

法二:
方法二类似PAT A1006 Sign In and Sign Out的解法,不需要使用结构体数组，直接定义三个结构体变量，F,M,temp；F和M分别表示分数最高的女生和分数最低的男生，temp作为临时变量，根据性别来分别对F和M进行更新·

参考题解一:

#include<cstdio>
#include<algorithm>
using namespace std;
struct person{
	char name[12];
	char gender;
	char id[12];
	int grade;
}p[100],woman,man; 
bool cmp(person a,person b){
	return a.grade>b.grade;
}
int main(){
	int n;
	bool flagF=false,flagM=false; 
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%s %c %s %d",p[i].name,&p[i].gender,p[i].id,&p[i].grade);
	}
	sort(p,p+n,cmp);
	for(int i=0;i<n;i++){
		if(p[i].gender=='F'){
			flagF=true;
			woman=p[i];
			break;
		}
	}
	for(int i=n-1;i>=0;i--){
		if(p[i].gender=='M'){
			flagM=true;
			man=p[i];
			break;
		}
	}
	if(flagF)	printf("%s %s\n",woman.name,woman.id);
	else	printf("Absent\n");
	if(flagM)	printf("%s %s\n",man.name,man.id);
	else	printf("Absent\n");
	if(flagF&&flagM)	printf("%d\n",woman.grade-man.grade);
	else	printf("NA\n");
	return 0;
}

参考题解二:

#include<cstdio>
struct person{
	char name[11];
	char id[11];
	int score;
}F,M,temp;

void init(){
	F.score=-1;\\设置女生分数为最低
	M.score=101;\\设置男生分数为最高
}
int main(){
	init();
	int n;
	char gender;
	scanf("%d",&n);
	while(n--){
		scanf("%s %c %s %d",temp.name,&gender,temp.id,&temp.score);
		if(gender=='M'&&temp.score<M.score){
			M=temp;
		}
		if(gender=='F'&&temp.score>F.score){
			F=temp;
		}
	}
	if(F.score==-1)printf("Absent\n");
	else printf("%s %s\n",F.name,F.id);
	if(M.score==101)printf("Absent\n");
	else printf("%s %s\n",M.name,M.id);
	
	if(F.score==-1||M.score==101)printf("NA\n");
	else printf("%d",F.score-M.score);
	return 0;
}