loops (USACO Humble Numbers 第n大元素)

loops (USACO Humble Numbers 第n大元素)

目要求是使用给定的一组质数为基，生成一组数，求生成数从小到大排序后的第n个元素。其中质数至多有100个，求的元素至多第是10,000个。

如给定的质数是{2,3,5}，则生成的数组为{2,3,2*2,5,2*3,2*2*2,3*3,2*5….}

我最初的想法是，求大于某值的下一个符合要求的数。在求下一个数时用搜索的方法，通过记录已经得到的结果可以很快的求得下一个数。然而数的范围很大，最高可以是2^30次，用vector<bool>没法记录结果。

随后注意到两件事儿，第一，生成的数字绝对不会重复，即生成数组中的每个数都可以唯一的用质数组生成，不存在两种不同的分解方法；第二，求的至多是第10,000个元素。

第一点说明DFS或者BFS都可以高效的产生符合要求的数，而且不会重复。第二点说明，如果已经有了10,000个符合要求的数字，同时知道这组数字的最大值，DFS或者BFS在产生数据时若大于该最大值就应该停止，若小于就应该加入到这组数据内，把过去最大的挤出去，得到新的最大值。

基于以上的分析，堆是不二人选，确切的说是最大堆，这样就可以实时的知道这组数内的最大值。若堆中元素不足n个，则直接插入；若已经有n个元素，同时插入的元素<最大元素，则弹出最大元素，插入新的元素。

所以只要DFS和BFS能尽可能少的产生数据，这个算法的时间复杂度不过是Ω(nlogn)，非常快。

第一次尝试是��序质数做DFS，第12个测试样例1.3s超时。想想因为DFS填充了太多的无用元素，队列的最大值太高，以至于剪枝失灵。所以把质数逆序排列做DFS，第12个测试样例0.8s通过。查看了一下答案，深感蛋疼，不是不好，就是看着有点儿累；于是重新用升序质数做BFS产生数据，因为这样可以迅速的填充相对最小的n个元素，使得剪枝可以早一点、狠一点，于是第12个样例0.065s通过。

至此问题圆满解决。

Read full article from loops (USACO Humble Numbers 第n大元素)