[Jobdu] 题目1214：丑数

题目描述：: 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

输入：: 输入包括一个整数N(1<=N<=1500)。

输出：: 可能有多组测试数据，对于每组数据，
输出第N个丑数。

样例输入：

样例输出：

很有技巧的一道题，注意分别为2，3，5维护一个index！

 #include <cstring>

 #include <cstdio>

 using namespace std;

 int a[];

 int getMin(int a, int b, int c)

 {

     int tmp = a < b ? a : b;

     return c < tmp ? c : tmp;

 }

 void init()

 {

     int idx = , idx2 = , idx3 = , idx5 = ;

     int val;

     a[] = ;

     while (idx < ) {

         idx++;

         val = getMin(a[idx2]*, a[idx3]*, a[idx5]*);

         if (val == a[idx2] *) {

             idx2++;

         }

         if (val == a[idx3] *) {

             idx3++;

         }

         if (val == a[idx5] *) {

             idx5++;

         }

         a[idx] = val;

     }

 }

 int main()

 {

     int n;

     init();

     while (scanf("%d", &n) != EOF) {

         printf("%d\n", a[n]);

     }

     return ;

 }

 /**************************************************************

     Problem: 1214

     User: hupo250

     Language: C++

     Result: Accepted

     Time:10 ms

     Memory:1028 kb

 ****************************************************************/

巴特西

[Jobdu] 题目1214：丑数

最新文章

热门文章