UVA 136:Ugly Numbers

Jasonlin posted @ 2011年3月27日 11:24 in UVA , 2521 阅读

题目链接: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

 

  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter