pat排序算法题

PAT 排序算法题

  • 排序
  • 分析
    • 难度:
    • 1012
    • 1016
    • 1025
    • 1028
    • 1055
    • 1062
    • 1075
    • 1080
    • 1083
    • 总结

排序

1012. The Best Rank (25)-PAT甲级真题
1016. Phone Bills (25)-PAT甲级真题
1025. PAT Ranking (25)-PAT甲级真题
1028. List Sorting (25)-PAT甲级真题
1055. The World’s Richest (25)-PAT甲级真题
1062. Talent and Virtue (25)-PAT甲级真题
1075. PAT Judge (25)-PAT甲级真题
1080. Graduate Admission (30)-PAT甲级真题
1083. List Grades (25)-PAT甲级真题

分析

难度:

		 难度:
		 p1016>p1055>p1075=p1080>p1062>p1083>p1012=p1025=p1028

1012

题目大意: 现已知N个学生的三门成绩, 平均分可以从这三门成绩得出。**分别
按照这4个标准**进行从高到低排序,得到排名。**K个查询**, 输出每个学生的
最好排名和这个排名对应的学科。如果有两个以上排名相同,那么按照A>C>M>E的
顺序输出。

基本要掌握的:
	一个循环得到排名
	4个排名如何得到最优结果
	4个排序如何使用一个循环解决。
	按学生ID得到对应位置数组下标。
	排序比较器的写法

难度:水题

1016

题目大意:现已知N个人的通话记录,和每个时间段的1分钟通话费用。求出这N个
人每次通话时长和费用,以及总费用。输出结果按照姓名的字母从小到大排序,
每个人的通话记录按照时间排序。

基本要掌握的:
	寻找匹配通话记录
	编写得到通话费用和通话时长的函数。累加或者从零作差法。
	比较器写法。
难度:中等, 细节繁琐。

1025

题目大意:现有N个考场,每个考场有若干个学生,给出每个学生成绩,输出每个学
生的ID,考场号,总排名,考场内排名。

分析:先按照考场内排名 然后赋值给总数组fin,然后总排名,最后输出。注意相同
的分数情况下按照学号的从小到大排列,但是他们的排名应该是一样的数字
难度:水题。

1028

题目大意: 给你N个记录,每个记录3列。输入列号C, 根据列号对这个N个记录排序。查找:输出所有。

难度:水题

1055

题目大意: 世界最富有的人,先已知N个关于富豪的记录, 姓名,年龄,财富值。
接着是k个查询,每次查询要求输出在某个特定年龄范围的TOP-K个富豪排名。
分析:	不能先按照年龄排序然后得到再按照财富排序。我一开始就是这个思路,
结果测试点1老是超时。因为N和M数量级差别大。所以按财富值排序,在循环中
只留下相同年龄的前100个人,因为这个100以后的人永远不会输出。最后从选出
那些在特征范围的富豪。
难度:中等,坑题

1062

题目大意:输入第1行给出3个正整数,分别为:N为考生总数;L为录取最低分数线,
即德分和才分均不低于L的考生才有资格被考虑录取;H为优先录取线——德分和才分
均不低于此线的被定义为“才德全尽”,此类考生按德才总分从高到低排序;才分不到
但德分到线的一类考生属于“德胜才”,也按总分排序,但排在第一类考生之后;德
才分均低于H,但是德分不低于才分的考生属于“才德兼亡”但尚有“德胜才”者,按总
分排序,但排在第二类考生之后;其他达到最低线L的考生也按总分排序,但排在
第三类考生之后。输出第1行首先给出达到最低分数线的考生人数M,随后M行,
每行按照输入格式输出一位考生的信息,考生按输入中说明的规则从高到低排序
。当某类考生中有多人总分相同时,按其德分降序排列;若德分也并列,则按
准考证号的升序输出~

分析:用结构体存储。写好cmp函数~结构体数组vector v[4]中v[0]保存第一类考生,
v[1]保存第二类考生…以此类推~写好cmp函数很重要,cmp函数中
,排序先按照总分排序,然后按照德分排序,最后按照准考证号排序…最后输
出符合条件的结果~

难度: 水题

1075

题目大意:现在已知N个学生,K个题目, M次提交结果。提交记录包括题号,和
得分。按排名,完美解题数量,id号排序输出学生的总排名,总分数,每个题目
得分。

分析:对于一次没提交的或者一次都没过的不显示。‘-’: 仅仅是没提交的,没过
编译器的为0。所以0有两种含义。

难度: 中等,坑

1080

题目大意:研究生录取。

分析: 排名后学生数组下标和ID不是一回事。段错误出现在排序。

难度:中等,坑

1083

题目大意:给出n个考生的信息,按照分数从高到低排序,并且输出给定区间的考生
信息。如果不存在满足条件的考生就输出NONE

分析:建立结构体数组,将不满足条件的学生grade改为-1,并统计满足条件的学
生的个数cnt,然后进行排序,输出前cnt个考生的信息~

注意:因为每个学生的成绩都不同,所以按照下降排列即可,return a.grade > 
b.grade;
题目: 水题

总结

	遇到排序题不要慌, pat上排序算法题变化的情况很多,但是万变不离其
宗,要清楚最简单的排序题怎么出的?而那些难题都是在这个基础上展
开的。
	排序查找题, 处理过程一般是先输入数据, 排序,建立索引
表,查找。

你可能感兴趣的