UVA-136 Ugly number

UVA传送门
<mark>题目大意</mark>
丑数是指不能被2，3，5以外的其他素数整除的数。把丑数从小到大排列起来，结果如下：
1,2,3,4,5,6,8,9,10,12,15……
求第1500个丑数
<mark>输出</mark>
The 1500’th ugly number is .
这道题有一个比较大的坑点就是输出中不用尖括号

AC代码

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int i = 0, j = 0, k = 0;
    long long a[1505];
    a[0] = 1;
    long long temp;
    for(int v = 1; v < 1500; v++)
    {
        if(a[i] * 2 > a[j] * 3)
            temp = a[j] * 3;
        else if(a[i] * 2 < a[i] * 3)
            temp = a[i] * 2;

        if(temp > a[k] * 5)
            temp = a[k] * 5;
            a[v] = temp;
        if(temp == a[i] * 2)
            i++;
        if(temp == a[j] * 3)
            j++;
        if(temp == a[k] * 5)
            k++;
    }
// for(int i = 0; i <= 10; i++)
// {
// cout << a[i] << " " ;
// }
   printf("The 1500'th ugly number is %d.\n", a[1499]);
}
================================================================================================================================================================================================================================================
//优先队列解题法
#include<iostream>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int a[] = {2, 3, 5};
int main()
{
    priority_queue< long long, vector<long long>, greater<long long> >q;
    set<int>s;
    q.push(1);
    s.insert(1);
    for(int i = 1; ; i++)
    {
        long long  x = q.top();
        q.pop();
        if(i == 1500)
        {
            cout<<"The 1500'th ugly number is "<<x<<"."<<endl;
            break;
        }
        for(int j = 0; j< 3; j++)
        {
            long long  m = x * a[j];
            if(!s.count(m))
            {
                s.insert(m);
                q.push(m);
            }
        }
    }
}

** 这道题 的思路就是枚举，每一个丑数都是由先前的丑数乘上2 3 5得到的**

原创转载请注明出处