UVA 136：Ugly Numbers

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=72

题目大意：

      素数因子只有2、3、5的数叫做丑数，求出第1500个丑数。

解题思路：

      因为指定要第1500个，我们先在我们机子上用暴力求出来然后直接输出，这种方法是比较投机取巧的，暴力花的时间非常久，要是提交暴力代码就TLE无疑啦。后来想到用优先队列（STL的priority_queue实现），从1开始放对队列，每次把最小的取出来然后乘以那三个数后放入队列，取到1500个数就结束。但是这样会有个问题，会有重复数据，后来保留上次取的数据，取出数据和上次取的数据判断一下，要是相同不做任何操作再取出下一个数据，要是不相同就保留这次的数据再取下一次。第1500次不相同的数据输出结果。

解题代码：

#include<iostream>
#include<queue>
using namespace std;
#define N 1500
typedef long long ll;
int s[3]={2,3,5};
priority_queue<ll,vector<ll>,greater<ll> > pq;
int main(){
	ll t,p=0,n=0;
	pq.push(1);
	while(n<N){
		t=pq.top();
		pq.pop();
		if(p!=t){
			p=t;
			n++;
			for(int i=0;i<3;i++){
				pq.push(t*s[i]);
			}
		}
	}
	cout<<"The 1500'th ugly number is "<<t<<'.'<<endl;
}

扩展知识：http://www.cppblog.com/CodeStream/archive/2011/03/25/142700.html

• 全局相关文章
• 相关文章