当前位置:首页 > 数据结构 > > 正文
SSOJ1111丑数[USACO]
118+

题目大意:有n个质因子,他们凑出的合数中,第m小是多少?

题目描述

对于一给定的素数集合 S = {p1, p2, …, pK},考虑一个正整数集合,该集合中任一元素的质因数全部属于S。这个正整数集合包括,p1、p1*p2、p1*p1、p1*p2*p3…(还有其它)。该集合被称为S集合的“丑数集合”。

注意:我们认为1不是一个丑数。

你的工作是对于输入的集合S去寻找“丑数集合”中的第N个“丑数”。所有答案可以用longint(32位整数)存储。

补充:丑数集合中每个数从小到大排列,每个丑数都是素数集合中的数的乘积,第N个“丑数”就是在能由素数集合中的数相乘得来的(包括它本身)第n小的数。

输入

第 1 行: 二个被空格分开的整数:K 和 N , 1<= K<=100 , 1<= N<=100,000.

第 2 行: K 个被空格分开的整数:集合S的元素

输出

单独的一行,输出对于输入的S的第N个丑数。

样例输入

4 19
2 3 5 7

样例输出

27

解题思路

首先将质因子全部放入小根堆中,堆顶即最小值。出堆后,下一个最小值可能是谁?就是堆中最小元素,或者这个最小值乘以最小的质因子。由于乘以其他质因子,也可能是后面需要用到的,所以我们干脆全部入堆,这样,每出来一个,进去100个,至多10000100个,手写堆不超时。

程序实现

如果想用优先队列,必须要进行优化,如去重。上面的代码,肯定有重复的元素,如2处理会乘以3,3出来也会乘以2。怎么避免这种情况?我们可以考虑最小质因子。出堆后,不要乘以所有质因子,只乘质因子不超过自己最大质因子的。这样就不会重复,也不会遗漏。

结构体中,a记录元素的值,p记录他的最大质因子,它维护的是最大质因子为p的所有合数的队列。

当然,还可以用单调性优化。我们可以依次计算出第i小。对于第i小,肯定是之前的i-1个元素,乘以一个质数。我们可以暴力枚举每个质数,乘以之前的i-1个元素。显然,每个质数的队列,具有单调性。由于之前维护的是正确的,所以不超过第i-1个的就是重复的,超过第i-1个的就有可能是答案,打擂台即找到答案。利用单调性,之前小的后续也是重复,不需要重复遍历。这样,每个质数至多乘以m个丑数,总的时间复杂度就是O(m*n)。

SSOJ1111丑数[USACO]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter