UVA-136 丑数题解答案代码算法竞赛入门经典第二版

187 阅读 0 评论 124 点赞

我是靠谱客的博主眼睛大鲜花，这篇文章主要介绍UVA-136 丑数题解答案代码算法竞赛入门经典第二版，现在分享给大家，希望可以做个参考。

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典例题和习题答案刘汝佳第二版

AC代码

#include<iostream>
#include<set>
#include<queue>

using namespace std;

int main() {
	set<long long> se;
	int arr[3] = {2,3,5};
	long long ll, llt;
	priority_queue<long long, vector<long long>, greater<long long> > pq;
	int i, j;
	se.insert(1);
	pq.push(1);
	for(i = 1; i < 1500; ++i) {
		ll = pq.top();
		pq.pop();
		for(j = 0; j < 3; ++j) {
			llt = ll * arr[j];
			if(se.count(llt) == 0) {
				se.insert(llt);
				pq.push(llt);
			}
		}
	}
	cout << "The 1500'th ugly number is " << pq.top() << '.' << endl;
	return 0;
}