【数据结构】poj 1338 （pair，priority_queue）

题目链接：点击打开链接

题目分析：找出第n的丑数，所谓丑数，即只含2，3，5的质因子；

随便怎样暴力都可以，但是学习了下数据结构

1. priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数:
priority_queue<Type,Container,Functional>

greater<>,is a kind of binary predicate,strict weak ordering :x<y

模板：

priority_queue<int,vector<int>,greater<int> >a;
priority_queue<int,less<int> > b;

如果写
priority_queue<int,greater<> >a;
priority_queue<int,less<> > b;

有时编译不过= =，error: wrong number of template arguments (0,should be 1)

2.switch（）

{

case x: ;break;

case y: :break;

}//注意！case并不是条件判断语句，只是进入此的端口，若没有break；就顺序执行

3。pair<long long,int>

#include<iostream>
#include<queue>
#include<vector>
#include<cstdio>
#define MAXN 1505
using namespace std;
typedef pair<long long,int> node;
long long ans[1505];
int main()
{
    int i,n;
    priority_queue<node,vector<node>,greater<node> >Q;
    Q.push(make_pair(1,2));
    for(i=1;i<=MAXN;i++)
    {
        node p=Q.top();
        Q.pop();
        switch (p.second)
        {
            case 2:Q.push(make_pair(p.first*2,2));
            case 3:Q.push(make_pair(p.first*3,3));
            case 5:Q.push(make_pair(p.first*5,5));
        }
        ans[i]=p.first;
    }
    while(scanf("%d",&n)!=EOF&&n)
    {
        printf("%lldn",ans[n]);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!