- 题目描述:
-
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
- 输入:
-
输入包括一个整数N(1<=N<=1500)。
- 输出:
-
可能有多组测试数据,对于每组数据,
输出第N个丑数。
- 样例输入:
-
3
- 样例输出:
-
3
很有技巧的一道题,注意分别为2,3,5维护一个index!
1 #include <cstring> 2 #include <cstdio> 3 using namespace std; 4 5 int a[1501]; 6 7 int getMin(int a, int b, int c) 8 { 9 int tmp = a < b ? a : b; 10 return c < tmp ? c : tmp; 11 } 12 13 void init() 14 { 15 int idx = 1, idx2 = 1, idx3 = 1, idx5 = 1; 16 int val; 17 a[1] = 1; 18 while (idx < 1501) { 19 idx++; 20 val = getMin(a[idx2]*2, a[idx3]*3, a[idx5]*5); 21 if (val == a[idx2] *2) { 22 idx2++; 23 } 24 if (val == a[idx3] *3) { 25 idx3++; 26 } 27 if (val == a[idx5] *5) { 28 idx5++; 29 } 30 a[idx] = val; 31 } 32 } 33 34 int main() 35 { 36 int n; 37 init(); 38 while (scanf("%d", &n) != EOF) { 39 printf("%d\n", a[n]); 40 } 41 return 0; 42 } 43 44 /************************************************************** 45 Problem: 1214 46 User: hupo250 47 Language: C++ 48 Result: Accepted 49 Time:10 ms 50 Memory:1028 kb 51 ****************************************************************/