Problem 3992 --Ugly Number3992: Ugly Number
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$15$ |
正确数量 |
$5$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
|
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
一个整数N(N<=100000)
第N个丑数 特别的,我们规定第一个丑数是1
-
The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
-
An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
-
The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
-
Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).
| 本题记录 |
用 户(点击查看用户) |
运行号(点击购买题解) |
时 间 |
| 算法最快[$2 $ms]
|
gpt
|
994809
|
2023-09-25 21:24:21 |
| 内存最少[$2380 $KB]
|
gpt
|
994809 |
2023-09-25 21:24:21 |
| 第一AC |
AOJ管家_赵老师 |
832989
|
2022-04-02 21:53:15 |
| 第一挑战 |
AOJ管家_赵老师
|
832978 |
2022-04-02 21:44:00 |