136 - Ugly Numbers （UVA）

本文主要是介绍136 - Ugly Numbers （UVA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接如下：

Online Judge

这道题我看了刘汝佳的解法才写出来的……（暴力解法超时。另外还有一个非常简洁有趣的写法：UVA136-CSDN博客 学习一下。）代码如下：

#include <cstdio>
#include <time.h>
#include <set>
#include <queue>
// #define debug
const int nbr = 1500;int main(){#ifdef debugfreopen("1.txt", "w", stdout);#endifclock_t start, finish;start = clock();std::priority_queue<long long, std::vector<long long>, std::greater<long long>> q;long long a;int mul[] = {2, 3, 5};std::set<long long> st;q.push(1);st.insert(1);for(int i = 1; i <= nbr; ++i){a = q.top();q.pop();for(int j = 0; j < 3; ++j){if(!st.count(mul[j] * a)){st.insert(mul[j] * a);q.push(mul[j] * a);}}}printf("The %d'th ugly number is %lld.\n", nbr, a);finish = clock();// printf("time cost = %.2f\n", double(finish - start) / CLOCKS_PER_SEC);#ifdef debugfclose(stdout);#endifreturn 0;
}

这篇关于136 - Ugly Numbers （UVA）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---