0024 Ugly Numbers UVA - 136 算法竞赛入门经典系列源码解析 算法竞赛入门经典第2版 p120

Ugly Numbers UVA - 136

问题

代码

// 算法竞赛入门经典系列源码解析

// 算法竞赛入门经典第2版 p120
// 算法竞赛入门经典 习题与解答
// 算法竞赛入门经典 训练指南
// 算法竞赛入门经典 算法实现
/*
    Dreams never shine!
    It's you that shine while chasing your dreams :)
    JAYO!!
*/

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int coeff[3] = {2, 3, 5};

int main()
{
    priority_queue<LL, vector<LL>, greater<LL>> pq;
    set<LL> s;
    pq.push(1);
    s.insert(1);
    for(int i = 1; ; i++) {
        LL x = pq.top(); pq.pop();
        if(i == 1500) {
            cout << "The 1500'th ugly number is " << x << ".\n";
            break;
        }
        for(int j = 0; j < 3; j++) {
            LL x2 = x * coeff[j];
            if(!s.count(x2)) { s.insert(x2); pq.push(x2); }
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

总结

一心一意，一A一C，11月11日，坚持不懈！