整数相关处理

剪绳子

题目来源： acwing 25

题目内容

给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，2 ≤ n ≤ 58 并且m ≥ 2）。

每段绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1]…k[m]可能的最大乘积是多少？

例如当绳子的长度是8时，我们把它剪成长度为2、3、3的三段，此时得到最大的乘积为18。

样例

输入：8

输出：18

思路说明

实际为整数划分问题，应将绳子分成由2和3组成的段，且应尽可能分成更多长度为3的段。即如果长度mod 3后余数为2，则保留2，如果余数为1，则凑够4，分成2+2。

证明

将长度为n的绳子分为k段，即n = n₁ + n₂ + … + n_k。

1、若n_i ≥ 5，则有3 * （n_i - 3） ≥ n_i，因为此时 2 * n_i≥ 9 恒成立。

2、若n_i = 4，则4 = 2 * 2，即将4 = 2 + 2可获得最大乘积。

3、分成的段中不可能有3个以上的2，因为2 * 2 * 2 < 3 * 3。

代码实现

class Solution {
public:
    int maxProductAfterCutting(int length) {
        if(length <= 3) {
            return 1 * (length - 1);
        }
        int ans = 1;
        if(length % 3 == 1) {
            ans *= 2 * 2;
            length -= 4;
        }
        if(length % 3 == 2) {
            ans *= 2;
            length -= 2;
        }
        while(length) {
            ans *= 3;
            length -= 3;
        }
        return ans;
    }
};