POJ—1338-丑陋的数字

题目大意

只有2、3或5是质因数的数字是丑陋的数字。
比如：1、2、3、4、5、6、8、9、10、12、…
给定整数 n，打印第 n 个丑陋的数字。

知识点

1 lower_bound:

1.1 参数：
first,last: 迭代器在排序序列的起始位置和终止位置，使用的范围是[first,last)。
val: 在[first,last)下，找到大于等于val值的位置。
1.2 返回值：
返回一个指向第一个大于等于val的位置的迭代器。
1.3 函数作用：
有序的情况下，函数返回指向第一个值不小于val的位置，也就是返回第一个大于等于val值的位置。（通过二分查找）。
1.4 举例：

	vector<int> v= {3,4,1,2,8};
	sort(v.begin(),v.end()); 先排序： 1 2 3 4 8
	
	// 定义两个迭代器变量 
	vector<int>::iterator iter1;
	vector<int>::iterator iter2; 
	
	iter1 = lower_bound(v.begin(),v.end(),3);//迭代器指向3
	iter2 = lower_bound(v.begin(),v.end(),7);//迭代器指向8（因为第一个大于等于8）
1
2
3
4
5
6
7
8
9

2 priority_queue:

//大顶堆(top更大)
priority_queue<int> a; 
priority_queue<int, vector<int>, less<int> > a;
    
//小顶堆
priority_queue<int, vector<int>, greater<int> > c; 
1
2
3
4
5
6

思路

通过将前面的数字*2，*3，*5，获得所有的 ugly 数字，再存储到向量 v 里：

1. 最开始将数字 1 加到队列中
2. 弹出队列中最小的数字 x ，将该数字存储到向量 v 中；
3. 将x2，x3，x*5的数字加入队列中。

但是上述思路还存在一个小问题，就是会出现重复的数字，比如6=2*3=3*2
因此在将 x 加入向量 v 之前还需要进行一个判断：
借助函数lower_bound判断向量 v 中是都存在了数字 x ，如果存在了就不再加入向量 v 和队列了。

AC代码

#include
#include
#include
#define ll long long 
using namespace std;
ll n,x;
vector<ll> v;
void solve() {
	priority_queue<ll, vector<ll>, greater<ll> > Q;
	Q.push(1);
	while(v.size()<1505) {
		x=Q.top();Q.pop();
		ll index=lower_bound(v.begin(),v.end(),x)-v.begin();
		//这样是为了排除重复的数字，比如6=2*3=3*2 
		//如果x存在，则获得x在向量里的下标
		//若 x 不存在，则返回的是大于x的下标（有可能是末尾） 
		if(index==v.size()||v[index]!=x) { //不重复
			v.push_back(x);
			Q.push(x*2);
			Q.push(x*3);
			Q.push(x*5);
		}
	}
}
int main() {
	solve();
	while(cin>>n&&n) {
		cout<<v[n-1]<<"\n";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30