UVA136 Ugly Numbers

       我们定义丑数为只含有$2,3,5$质因子的数，例如$6=2\times3$，所以$6$是丑数，$14=2\times7$，所以$14$不为丑数。$1$也为丑数，请求出第$1500$个丑数是多少？

        

        我们很容易想到暴力算法，枚举每个数看它是不是丑数，然后计数即可。

       

#include <bits/stdc++.h>

using namespace std;

  

int n=1500,cnt=0;

  

int main()

{

　　for(int i=1; ;i++)

　　{

　　　　int t=i;

　　　　while((t&1) == 0) 

　　　　　　t >>= 1;

　　　　while(t%3 == 0)

　　　　　　t /= 3;

　　　　while(t%5 == 0)

　　　　　　t /= 5;

　　　　if(t == 1)

　　　　　　cnt++;

　　　　if(cnt == n)

　　　　{

　　　　　　printf("The %d'th ugly number is %d.\n",n,i);

　　　　　　break;

　　　　}

　　}

　　return 0;

}




       时间不够，怎么办？直接输出结果 

       我们可以想到，除1以外的丑数都是通过一个丑数分别$\times2,3,5$得到，我们只要把得到的丑数放入队列，然后排序一下就好了。可排序又大大增加了时间复杂度，问题来了，怎么不通过排序保证主队列中的丑数单调递增呢？

       将$1$放入主队列，建3个队列$q_2,q_3,q_5$分别表示$\times2,3,5$得到的丑数。$q_2,q_3,q_5$各自进$1\times2,1\times3,1\times5$的值。

        我们可以肯定，$q_2,q_3,q_5$最前面的数肯定比后面的大（因为后面的晚入队）,只需要比较$q_2,q_3,q_5$最前的数，将最小的数出队，放入主队列中，再在$q_2,q_3,q_5$放入它$\times2,3,5$的倍数就好了！值得一提的是，如果有两个或更多最小数，需要一起出队。当计数到$1500$时输出。（别忘了输出最后有句号）

上代码: 

#include <bits/stdc++.h>

using namespace std;

  

int n=1500,cnt=2;

queue<int> q2,q3,q5;

  

int main()

{

　　q2.push(2);

　　q3.push(3);

　　q5.push(5);

　　if(n == 1)

　　　　return printf("The %d'th ugly number is %d.\n",n,n),0;

　　while(1)

　　{

　　　　int x2=q2.front(),x3=q3.front(),x5=q5.front();

　　　　int minn=min(x2,min(x3,x5));

　　　　if(cnt == n)

　　　　{

　　　　　　printf("The %d'th ugly number is %d.\n",n,minn);

　　　　　　break;

　　　　}

　　　　cnt++;

　　　　if(x2 == minn)

　　　　　　q2.pop();

　　　　if(x3 == minn)

　　　　　　q3.pop();

　　　　if(x5 == minn)

　　　　　　q5.pop();

　　　　q2.push(minn << 1);

　　　　q3.push(minn*3);

　　　　q5.push(minn*5);

　　}

}