NOIP2007普及组解题报告
By江苏省赣榆县实验中学初二参赛选手夏雨阿洛c
我仅仅想用本文启发一下NOIP2007普及组的同学们，我也不是什么牛，仅仅是意见交流，另：本文供各位路过的牛们鄙视下。普及组的同学们，我也不是什么牛，仅仅是意见交流，本文供各位路过的牛们鄙视下。
第一题：奖学金【题目描述】：【解题思路】：这一题有很多种做法，包括排序、模拟等等。现在，介绍一种最优算法，（其实最烂算法也可以全过，数据规模毕竟很小，呵呵）2时间复杂度：空间复杂度：插排（时间复杂度：平均ON最坏ON空间复杂度：O1。最坏空间复杂度。）思路：1开一个结构类型Pascal里是record，CC是struct，包含了学号信息，总分成绩，语文成绩。或者也可以开三个以下标为关联的一维数组，一次表示上述三个参数。2读入。每当读入一行信息，调用过程i
sert，从前向后依次寻找，直到寻找到某一记录的总分比当前读入总分小，或其总分和当前读入总分相等且语文成绩比当前总分小，则在当前位置插入所读入的数据。（这个插入可以是将后面的数据依次向后移动一位，也可以是通过链表的方法实现。）3输出，从1至5，输出学号和总分即可。还有一点要注意的是，当总分相等，且语文成绩也相等的时候，就要将学号小的排在前面。【解题感想】：对于这种送分题，千万不要辜负出卷人的期望，能拿到的分数就一定要拿到。否则既对不起老师，也对不起出卷人，更对不起自己。读题目的时候千万要仔细，我同学就是因为这一题的语文处理有点问题而白白掉了3个点。第二题奖品分组【题目描述】：【解题思路】：这一题乍一看起来，像是动态规划，很多选手被问题的“最”字迷惑了，拿到题目就开始乐呵呵的DP殊不知，此题如用动归来做，确实是可以实现的，但编程复杂度很高。下面介绍一种简单易行的方法：简单哈希表贪心贪心哈贪时间复杂度：简单哈希表贪心哈贪（时间复杂度：平均ON最坏ON2空间复杂度O1）最坏空间复杂度）思路：1开一个a1200的数组作为桶，至于类型I
teger足够用了，因为即使最坏情况所有的数据都在一个桶里，也不过是30000个。_还要有一个标记，用来标记当前物品是否找到配对以及一个sum用来记录组数。2依次读入，哈希表当前定义为FKey
也就是类似基数排序的那样啦。3读入完毕后，从最大的下标开始用一个For循环，伪代码如下：fori桶最大的下标dow
to1whileai0dobegi
标记变成Falseforj每组最大的限制idr