[Jobdu] 题目1214:丑数

时间:2022-12-17 20:44:46
题目描述:

把只包含因子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 ****************************************************************/