PAT 解题报告 1055. The World’s Richest (25)

题目描述:

抽象成数据库的查询问题就是, 高效的实现

select *

from table

where `age`  is between [Amin, Amax]

ordered by `财富` decreasing, `age` increasing, `name` increasing

limits M

找到在某一个年龄范围内的所有富豪里面的前M个最有钱的,并且按照给定的顺序输出。

算法分析:

方法一: 暴力, 全局给这个table排序, 按照那个财富, age, name的顺序, 然后剔除每个年龄中财富排名在一百以后的那些人, 因为这些人永远不可能被返回, M <= 100,  剩下的table 的大小最大也就是 200 * 100, 对每一个查询, 线性扫描这个剩下的table, 输出之多M个富豪.  有点小优化就是剔除那些排名100以后的. 使得搜索的空间减小了. 但是如果年龄的范围很大这个方法可能不适用.

方法二: 先算出所有结果,然后针对每个查询直接输出结果, 理由是查询的条件是有限的, (用那些比较小的有限的常量来bound查询时间比用那些比较大的来bound可以获得更好的时间效率, 相比查询的个数, 查询条件本身的数量似乎更少), 大概方法是先对财富排序, 在对年龄排一次序,  然后求出每种可能的年龄区间的结果集, [1, 1] [1, 2] …. [1, 200] ….[199, 200], [200, 200], 求这个结果集可以用dp的思路, 因为[i, j] = merge([i, j-1], [j, j]).

总结:

PAT 解题报告 1055. The World’s Richest: 找到在某一个年龄范围内的所有富豪里面的前M个最有钱的,并且按照给定的顺序输出: 暴力法会超时, 采用查表和dp的思路先算出所有结果.

Written on April 7, 2013