题目描述
��panda是个数学怪人，他非常喜欢研究跟别人相反的事情。最近他正在研究筛法，众所周知，对一个范围内的整数，经过筛法处理以后，剩下的全部都是质数，不过panda对这些不感兴趣，他只对被筛掉的数感兴趣，他觉得在这些被筛掉的数中一定隐藏着重要的宇宙秘密，只是人们还没有发现罢了。
��panda还觉得如果只是单纯地从小到大筛的话，还不足够发现其中的奥秘，于是他决定对至多只包含某些质因数的数进行研究（比如说至多只包含质因数2，3的数有2,3,4,6,8,9,……），他需要得到这些数中第k小的数（k是panda认为的宇宙系数），请你编个程序，帮助他找到这个数。
输入输出格式
输入格式：
��第1行有2个数n,k，n代表质因数的个数，k代表那个宇宙系数（1<=n<=100，1<=k<=100000）
��第2行有n个数，代表这n个质因数。（每个均小于1000，且不相同）
输出格式：
��仅1行，即至多只包含这n个质因数的数中第k小的数。（这个数不会超过2000000000）
输入输出样例
2 7 3 5
45
说明
样例说明：前6个分别是3，5，9，15，25，27。
分析：一个想法是维护一个优先队列，每次取最小值和所有素数相乘,结果放进优先队列里直到出现k个元素，这样也可以拿到很高的分数，但是不是最好的，对于可以用优先队列做的题，有一个非常常用的方法就是把优先队列转化为普通队列.such as:noip2016蚯蚓，只要想方设法把一个队列变成单调的队列就好了，那么这道题怎么变呢？
先把所有的质数依次放到队列里，一开始是单调的，我们要用优先队列的方式来维护，当一个质数乘了第i个元素后，它下一个乘的一定是第i+1个元素，而且保证结果是单调的。每个质数乘一下后会得到多个质数，找到最小的那个数，插入队列里，在插入之前要先判一下重.
这个判重有点小技巧，我一开始想着一个bool数组，可是太大了开不下，map似乎也不行，其实这个队列是单调的，我们只需要看队尾元素有没有重复就好了......
优先队列---->“单调队列”，神奇的优化.而这个优化的关键，就是我们要如何让它单调，像优先队列一样操作.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <cmath> #include <map> using namespace std; const int inf = 2000000000; int n,k,prime[110],q[100010],tot,mx; int cnt[110],cc; map <int,int> flag; int main() { scanf("%d%d",&n,&k); for (int i = 1; i <= n; i++) scanf("%d",&prime[i]); q[++tot] = 1; for (int i = 1; i <= n; i++) cnt[i] = 1; while (tot != k + 1) { mx = inf; for (int i = 1; i <= n; i++) { int t = q[cnt[i]] * prime[i]; if (t < mx) { cc = i; mx = t; } } cnt[cc]++; if (mx != q[tot]) q[++tot] = mx; } printf("%d ",q[k + 1]); return 0; }