首页 > 其他 > 详细

PAT1012

时间:2019-09-20 14:31:41      阅读:112      评论:0      收藏:0      [点我收藏+]

整体思路

  这道题看下来就是比较简单的模拟题,穿插了对排序和查找的考察。

  (1)存储:由于一个学生对象是有ID以及多个成绩信息,所以用自定义的结构体student来存储信息。多个学生就使用一个结构体数组std来存储。

  (2)排序:我们调用<algorithm>库中的sort函数,基本就是O(nlogn)的复杂度,自己写个描述排序规则的cmp函数即可。排序完,整个std数组就会按照我们的规则乖乖排好了,因为我们会有多次排序,所以每              一次的排序结果都要记录下来,那这个时候每一次排序结果要存储在哪里??就是一个问题,这个问题也是这道题的一个难点,这直接关系到下一个步骤——查找的效率!!

   好啦,想想我们是靠什么来查找的呢??是学生的ID号对吧,如果我们查找的时候能够按照ID号来对号入座,使用hash的方法,那时间复杂度就为O(n),即使在全部人都要一起来查找的情况下,算法也有            很好的表现,对比起暴力查找方法O(n^2),简直就是人生赢家有木有(手动狗头)

  (3)查找:如此一来,在解决完排序的存储方式问题后,查找就是很自然的事,直接就用ID去哈希一下就OK啦!

避坑指南

  这道题还是有一丢丢的小坑的,不得不说细节还是很重要的,平时多练多总结,见得多的,练的熟了,自然避坑能力就会逐渐提高。

  (1)排名的方式:12225(?)   12223(?)

PAT1012

原文:https://www.cnblogs.com/chuan-chuan/p/11556090.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!