例题5-7 UVa136 Ugly Numbers（STL：priority_queue）

题意：

看白书

要点：

很简单的priority_queue应用题。之所以写个博客是为了总结一下priority_queue的写法。主要问题是VS中greater不是模板，但OJ中可以AC。

需要特殊排序可以有以下两种写法：

struct node
{int x, y;
};
struct cmp
{bool operator()(node a, node b){return a.x > b.x;//注意这里是优先度的意思，如果想从小到大输出要>}
};
priority_queue<node, vector<node>, cmp > p;

或者：

struct node
{int x, y;friend bool operator<(node a, node b){return a.x < b.x;//这里直接重载了<，所以优先度就是从小到大的}
};
priority_queue<node> pq;

#include<iostream>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
const int coff[3] = { 2,3,5 };struct cmp//升序排列
{bool operator()(LL &a, LL &b)//仿函数{return a > b;}
};int main()
{//priority_queue<LL, vector<LL>, greater<LL> > pq;priority_queue<LL, vector<LL>, cmp > pq;//VS2015中greater不行但OJ中可以ACset<LL> s;pq.push(1);s.insert(1);for (int i = 1;; i++){LL x = pq.top();pq.pop();if (i == 1500){printf("The 1500'th ugly number is %lld.\n", x);break;}else{for (int i = 0; i < 3; i++){LL temp = x*coff[i];if (!s.count(temp)){s.insert(temp);pq.push(temp);}}}}return 0;
}