题目链接：?pid=1058
题意：丑数是指只有2,3,5 or 7这几个素因数的数（所以1也是丑数），找到第n个丑数。
思路：除了2，3，5，7任何一个丑数都是由另一个丑数乘上2，或3，或5，或7得到的。
所以可以用优先队列，每取出一个丑数就入队他们乘上2，3，5，7得到的四个丑数，这样每个丑数都生成了。复杂度还是不错的，不过按这种方法会生成比较大的数，最终爆掉int，所以要用long long
//93MS 1228K #include<cstdio>#include<cstring>#include<queue>#define ll long longusing namespace std;ll ans[6000];int main(){priority_queue<ll,vector<ll>,greater<ll> >que;que.push(1);int cnt=0;while(!que.empty()){if(cnt==5842) break;ll t=que.top();que.pop();if(t<=ans[cnt]) continue;ans[++cnt]=t;que.push(t*2);que.push(t*3);que.push(t*5);que.push(t*7);}int n;while(~scanf("%d",&n)&&n){if(n%10==1&&n%100!=11)printf("The %dst humble number is %I64d.\n",n,ans[n]);else if(n%10==2&&n%100!=12)printf("The %dnd humble number is %I64d.\n",n,ans[n]);else if(n%10==3&&n%100!=13) printf("The %drd humble number is %I64d.\n",n,ans[n]);else printf("The %dth humble number is %I64d.\n",n,ans[n]);}return 0;}还可以用尺取法：
每个丑数乘上2，3，5，7都会生成另一个丑数，而且第2个丑数一定是第一个丑数乘2，3，7，5得到的四个数中最小的，第三个丑数肯定是第一个丑数乘3，7，5（第一个丑数乘2已用掉）和第二个丑数乘2得到的四个数中的最小值。
可以看出把乘的2，3，7，5当作对象，每次生成下一个丑数一定是2，3，7，，5乘以当前最靠前的且没乘过的数。
所以用尺取法把四个乘数当成对象，设成4个坐标，初始化成1，一步一步向前推进，直到推进n次，复杂度O(N),很优。
//93MS 1112K #include<stdio.h>#include<algorithm>#include<cstring>using namespace std;int ans[5850];int main(){int n;int a,b,c,d;ans[1]=1;a=b=c=d=1;int m=1;while(m <= 5842){int tmp=min(min(2*ans[a], 3*ans[b]), min(5*ans[c], 7*ans[d]));//生成下一个丑数ans[++m]=tmp;//向前推进if(tmp==2*ans[a]) a++;if(tmp==3*ans[b]) b++;if(tmp==5*ans[c]) c++;if(tmp==7*ans[d]) d++;}while(~scanf("%d",&n) && n){printf("The %d",n);if(n % 10 == 1 && n % 100 != 11)printf("st");else if(n % 10 == 2 && n % 100 != 12)printf("nd");else if(n % 10 == 3 && n % 100 != 13)printf("rd");elseprintf("th");printf(" humble number is %d.\n",ans[n]);}return 0;}
我要扼住命运的咽喉。
