【2】丑数(优先队列)

丑数

Description

丑数是指素因子都在集合｛2，3，5，7｝内的整数，第一个丑数是1。

Input

输入n

Output

输出第n大的丑数。

Samples

Input

1

Output

1

AC CODE：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7; 
const int N = 4e5 + 10 ;
const int INF = 0x3f3f3f3f ;
priority_queue<ll ,vector<ll>,greater<ll> > q; 
ll f[4]={2,3,5,7};
unordered_set<ll> st;
int main(){
	st.insert(1),q.push(1);
	ll n,res;
	cin>>n;
	for(int i=1;i<=n;i++) {
		res = q.top();q.pop();
		for(int j=0;j<4;j++) {
			ll t = res * f[j];
			if(!st.count(t)) {
				st.insert(t);
				q.push(t);
			}
		}
	}
	cout<<res<<endl;
 	return 0;
}

解析：

很有意思的问题，知道了第一个丑数是1，每次把队首的元素输出就是第n大的丑数，那么如何保证队列里都是丑数，只需要把最小丑数 乘2，乘3，乘5，乘7 得到的数放进优先队列即可！

这样可以保证第n次输出的是第n大的丑数，并且不会错过任何一个，因为在队列里的数所能产生最小的数就是 队首元素 乘 2得到的数。

所以就能得到答案，这里为了防止重复的元素入队列，用到了unordered_set，因为unordered底层是哈希，他的增删查改都是O(1),因为不需要set排序，所以用这个是比较合适的！