【日常学习】【优先队列】POJ1338 Uva136 - Ugly Numbers题解

骑猪看日落 2022-08-07 00:23 116阅读 0赞

昨天夜里学了栈、队列和优先队列，栈还有的地方不大懂，队列基本可以，优先队列很高兴。本想今天上午继续弄这个，但是跟着李晨他们一块听了清华交院罗雨屏老师讲的计算几何= =虽然以我的水平听计算几何有点早，但至少是听懂了很多，感觉很高兴；十点多就没有再听，毕竟之后越来越深亚历山大。于是就来写一下丑数的题解。

题目：除2，3，5外不能被其他素数整除的数为丑数，求第1500个丑数（Uva版），求第n(n<=1500)个丑数（POJ版）

思路：第一个是1，放入升序优先队列（小的先出），之后每次出队第一个元素，即最小的，然后分别乘以2,3,5，判重，入集合；

Uva到1500停止即可；POJ我用了一个迭代器从头遍历set查找，其实如果建立一个平行的优先队列也可以，不过由于优先队列不能使用下标，还必须用迭代器，这么做就多此一举了。（MS关联容器都不能使用下标？）

先放代码：

//ugly numbers
    #include<iostream>
    #include<vector>
    #include<queue>
    #include<set>
    using namespace std;
    typedef long long ll;
    const int a[3]={2,3,5};
    
    int main(){
    	priority_queue<ll,vector<ll>,greater<ll> > pq;//REMEMBER!IT'S "> >",NOT ">>".此处>>之间应有空格，否则解释错误；另外vector<ll>是基类型，表示队列以vector形式存储；同志们表示也可以用双向队列【那是什么= =
    	set<ll> s;//集合用于储存已知的丑数，既可以判重，在POJ版本中也可以用来查找第n个
    	pq.push(1);//1入队
    	s.insert(1);//1入集合，注意用insert函数；此处由于是集合，插入后自动排序，不需要位置参数；有位置参数的时候insert是插入到指定位置前
    	for (int i=1;;i++){
    		ll x=pq.top();//取优先队列最先出队的元素，但这个元素是优先级最大的而不是最先入队的，所以用top,单纯的queue中用front
    		pq.pop();//队首元素出队
    		if (i>1500){
    			break;
    		}
    		for (int j=0;j<3;j++){
    			ll y=a[j]*x;
    			if (!s.count(y)){//集合判重
    				s.insert(y);
    				pq.push(y);
    			} 
    		}
    	}
    	int n;//从这里开始是poj版查找第N个
    	cin>>n;
    	while (n){
    		set<ll>::iterator it=s.begin();//迭代器指针设置到开始
    		for (int i=0;i<n-1;i++) it++;//找到指定位置；注意因为一开始是0位置，即第一个元素，应该加n-2次找到第n-1的位置，才是第n个元素
    		cout<<*it<<"\n";//和指针一样输出
    		cin>>n;
    	}
    	return 0;
    }

答案：859963392

今天，我们的同学们都放假了。

我们也想放假， 但我们还在坚持。

今天突然意识到我们每天从早上七点到晚上十点，一天十五个小时泡在机房里。

这是我们的寒假，或许很多很多的OIers都是这样，这是我们的生活。

我很高兴这种生活是我所喜欢的，我很高兴学到很多知识。

就要过年了，大家都新年快乐。

——商女不知亡国恨，隔江犹唱后庭花。