【USACO3.1.3】Humble Numbers丑数（蒟蒻解析）

（注：属于蒟蒻的分析，不存在高端代码操作，只有简单的实现过程）

【USACO3.1.3】Humble Numbers丑数

时间限制 : 10000 MS   空间限制 : 655360 KB；

问题描述

对于一给定的素数集合 S = {p1, p2, ..., pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1p2、p1p1、p1p2p3...(还有其它)。该集合被称为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                                                                                              27

2    3     5     7      

分析：

从求解的地方出发，我们可以看出，此题属于“求第k小”一类的问题。构造丑数本身并不困难，困难的地方在于寻找第k小。那么我们可以将问题化简为:几个数之间不断相乘，求出乘积的第k小。求乘积不难，搞定第k小就是问题的关键，怎样求出第k小呢？如果我一边把数放进去，一边排序，是不是就可以拥有有序的序列，然后求出第k小了呢？？？

沿着这个思路走，解法就已经很明朗了。其实就是一个放数+排序的循环。而对于这样的操作，我推荐使用优先队列（使用sort要慢一些，个人觉得比较难处理），如果不会系统自带的队列，自己也可以尝试手工队列。（priority_queue<int> q）

如何运用队列求出题解：

我们应该在写代码之前，先考虑这道题的边界条件和特殊数据，是用大根堆，还是小跟堆？可能很多朋友犯过这样一个错误：使用大根堆，当队列q.size（）==k的时候，就输出q.top()（有可能只有我自己而已emmm）；然后wa了很多个点。注意：这样的做法使你不能保证你队列中的数就是前k小，原因是因为，每一次相乘可能会产生比当前值较小，或者较大的数（好像没有把原因说清楚吧emmm）。举个列子吧（这个就很闲而易见了=v=）：

已知：丑数：2 3 5 7，求 ：第3小。

 如果按照原来大根堆的做法，就会直接输出5，实际上应该输出的是4（动动手吧，这里就不具体说明了）。怎样才能避免这样的问题呢？其实换一种思路，用小跟堆就可以了。因为两个数的乘积永远大于他们两本身，所以，最小的数的位置是不会变动的（如果不太理解，还是可以通过上面的例子进行手工操作一下就明白了）。每一次从队列中取出最小的数（这个时候不要pop），然后用最小的数去乘以队列中的所有数，将新获得的数重新入队，再pop；而取出的数，我们可以存在一个数组里面，当数组的长度达到k+1的时候，我们就得到第k小啦。

注意：有可能会有重复的数据输入进去，在这种情况下你可以尝试用set，或者手工排除的方式，我这里用的是手工排除进行说明：如果取出的数是<=当前数组的最大值，那么就表明我们已经取过这个数了，就不加入数组里面（还是手工试验一下吧，感觉我会越说越糊涂qwq）

接下来就是放代码了（果然这才是最轻松的部分······）

#include<cstdio>
#include<queue>
using namespace std;
long long int a[100002];
int b[101];
priority_queue<long long> q;
int main()
{
	//freopen("ceshi.in","r",stdin);
	int n,m;
	q.push(-1);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	int cnt=0;
	while (cnt<=m+1)
	{
		long long int x=q.top();
		x=-x;
		q.pop();
		while (a[cnt]<x)
		{
			cnt++;
			a[cnt]=x;
			for (int i=1;i<=n;i++)
			q.push(x*b[i]*-1);	
		}
	}
	printf("%d",a[m+1]);
	return 0;
}