JzxxOJ OnlineJudge

从现在开始,你的学生生活将是如此的不同。巨大的脑洞,丰富的题库,全面的测试用例,全新的视野,这一切,都让你的 Coder 生活更加精彩。

WJOJ OnlineJudge

新闻

2320-数的分解 解题报告-Shortway

最优化问题,尽量都分成3,不足部分就分成2。

对于 n < 4,可以验证其分解成几个正整数的和的乘积是小于 n 的。
对于 n >= 4, 能证明其能分解成几个数的和使得乘积不小于 n。
如果分解成 1 和 n - 1,那么对乘积是没有帮助的,因此,假设 n分解成 a 和 n - a,2 <= a <= n - 2,那么
a * (n - a) - n
= (a - 1) * n - a * a + a - a
= (a - 1) * (n - a) - a
>= (a - 1) * 2 - a
= a - 2
>= 0
如果 a, n - a 仍然 >= 4,那么继续分解,直至 a, n - a < 4。因为每次分解都能使乘积增加,所以最优解必是最终分解结果,也即分解出的数全是 2 或 3 。
(1)
假设 n 是偶数,且分解成 a 个 2 和 b 个 3,即 n = 2 * a + 3 * b,则乘积为 2a * 3b
注意到 23 < 32 且 2 * 3 = 3 * 2 = 6,所以每 3 个 2 换成 2 个 3 会使乘积更大,因此,
最优方案是分解成 n/6*2 个 3 和 n%6/2 个 2,乘积为 3n/6*2 * 2n%6/2
(2)
假设 n 是奇数,则一定需要分出一个 3,然后 n - 3 就是偶数。因此最优方案是分解出
(n-3)/6*2+1 个 3 和 (n-3)%6/2 个 2,乘积为 3(n - 3)/6*2+1 * 2(n-3)%6/2


与你一起发现更多精彩资源

coding 的世界等你来探索

还有另一个自己在这里等你

也许另一个人也和你一样,发现着自己的创新和诚心。

--> --> //;