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$的倍数就好了！值得一提的是，如果有两个或更多最小数，