1 条题解
-
0
何老师 (root) LV 0 MOD @ 2019-07-19 13:35:42
枚举:
设长方体的长宽高分别为: \(a,b,c\)(单位厘米),则 \(a,b,c\) 范围为:\(1..n\)。所以枚举 \(a,b,c\),每枚举一种方案,判断 \(a*b*c==n\) 成立否,成立则是一种合法方案,从中所有的合法方案中选择一个表面积最小的方案。
暴力的时间复杂度时 \(O(n^3)\),下面来优化:
1、当枚举 \(a,b\) 之后,根据等式 \(a*b*c=n\),有 \(c=n/(a*b)\),所以可以不枚举 \(c\);
2、当枚举 \(a\) 之后,\(b\) 的枚举范围时 \(1..n/a\)。
- 1