UVA 136 Ugly Number（优先队列）

深藏阁楼爱情的钟 2022-06-07 00:15 167阅读 0赞

# 题目 #

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 1500'th ugly number.

## Input and Output ##

There is no input to this program. Output should consist of a single line as shown below, with <number> replaced by the number computed.

## Sample output ##

The 1500'th ugly number is <number>.

# 思路： #

题目求第1500个丑数（因数只有2，3，5的数，包括1）。借用STL的优先队列，假设队列中有若干个丑数（初始值为1），每次取出队列中最小的丑数，判断其是否是第1500个。若不是，则用其乘以2，3，5，再入队（保证不重复，借用set.count来判断）。依此类推，当循环到i为1500的时候取出的丑数就是第1500个（因为每次取出的都是对立中最小的）。

#include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <set>
    #include <queue>
    #include <vector>
    #define ll long long
    
    using namespace std;
    
    int main()
    {
        priority_queue<ll,vector<ll>,greater<ll> >  q;
        set<ll> s;
        int a[3]={2,3,5};
        q.push(1);
        s.insert(1);
    
        for(int i=1;;i++)
        {
            ll t=q.top();
            q.pop();
            if(i==1500)
            {
                cout<<"The 1500'th ugly number is "<<t<<"."<<endl;
                break;
            }
            for(int j=0;j<3;j++)
            {
                if(!s.count(a[j]*t))
                {
                    q.push(a[j]*t);
                    s.insert(a[j]*t);
                }
            }
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，167人围观）

还没有评论，来说两句吧...

相关阅读

相关 Ugly Numbers UVA 136 丑数

解题思路：首先丑数是指不能被2,3,5以外其他素数整除的数。最小的丑数数1，对任意一个丑数x；则2x,3x,5x也都是丑数，一个丑数有多种生成方式，所以，每取出一个丑数都

Bertha 。/ 2024年02月17日 18:47/ 0 赞/ 71 阅读

相关 LeetCode-Ugly Number

Problem: > Write a program to check whether a given number is an ugly number. > Ugly

矫情吗；*/ 2022年08月17日 14:09/ 0 赞/ 21 阅读

相关【日常学习】【优先队列】POJ1338 Uva136 - Ugly Numbers题解

昨天夜里学了栈、队列和优先队列，栈还有的地方不大懂，队列基本可以，优先队列很高兴。本想今天上午继续弄这个，但是跟着李晨他们一块听了清华交院罗雨屏老师讲的计算几何= =虽然以我的

骑猪看日落/ 2022年08月07日 00:23/ 0 赞/ 111 阅读

相关 263 Ugly Number

public boolean isUgly(int num) { if (num == 0)//不要忘记num=0的情况

深碍√TFBOYSˉ_/ 2022年08月04日 08:44/ 0 赞/ 167 阅读

相关 263. Ugly Number

Write a program to check whether a given number is an ugly number. Ugly numbers are pos

短命女/ 2022年07月15日 01:28/ 0 赞/ 184 阅读

相关 264.Ugly Number II

/\ Write a program to find the n-th ugly number. Ugly numbers are positive numbe

比眉伴天荒/ 2022年06月09日 03:55/ 0 赞/ 158 阅读

相关 263.Ugly Number

/ Write a program to check whether a given number is an ugly number. U

- 日理万妓/ 2022年06月09日 03:54/ 0 赞/ 172 阅读

相关 UVA 12100 Printer Queue(队列，优先队列)

详细题目：https://vjudge.net/problem/UVA-12100 思路：用队列模拟，开一个<pri , pos> 的队列，分别表示任务的优先级

朱雀/ 2022年06月07日 02:26/ 0 赞/ 213 阅读

相关 UVA 136 Ugly Number（优先队列）

题目 Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1,

深藏阁楼爱情的钟/ 2022年06月07日 00:15/ 0 赞/ 168 阅读

相关 4. Ugly Number II

4. Ugly Number II Description Ugly number is a number that only have factors 2

╰+哭是因爲堅強的太久メ/ 2022年05月27日 07:29/ 0 赞/ 166 阅读