题目描述与示例

题目描述

一根X米长的树木，伐木工切割成不同长度的木材后进行交易，交易价格为每根木头长度的乘积。

规定切割后的每根木头长度都为正整数，也可以不切割，直接拿整根树木进行交易。

请问伐木工如何尽量少的切割，才能使收益最大化？

输入描述

木材的长度 (X<=50)

输出描述

输出最优收益时的各个树木长度，以空格分割，按升序排列

示例

输入

10

输出

3 3 4

解题思路

注意，本题和LeetCode343、整数拆分基本思路完全一致。

从1开始枚举树木长度X，寻找规律。

容易观察得出规律。

1. 尽量分成长度为3的小段，这样才能使得乘积的收益尽可能大。
2. 当X <= 4时，不进行切割。注意4不会被切割为2 2，因为虽然2 2也能得到4的总收益，但是并不是切割数最小的方式
3. 当X > 4且X % 3 == 0时，分成n // 3组长度为3的小段。
4. 当X > 4且X % 3 == 2时，分成n // 3组长度为3的小段，1组长度为2的小段。
5. 当X > 4且X % 3 == 1时，分成n // 3 - 1组长度为3的小段，1组长度为4的小段。

本题的贪心思想体现在，当我们可以将X切割为长度为3的小段时，就尽量去这样切割。

当若干个正整数的和为确定值时，他们乘积其实同时取决于这些正整数的数量和大小。根据基本不等式可知，这些数必须尽量接近，才能使得乘积尽可能大。

所以段数应该尽量被切成2或3的长度（不能切成1）。很容易观察发现切成长度为3比切成长度为2要更好。

X = 5，切成5 = 3+2。

X = 6，切成6 = 3+3就要比切成6 = 2+2+2要更好。

X = 7，可能的切法为7 = 3+4或者7 = 3+2+2或者 7 = 2+5。显然 7 = 2+5不如7 = 3+2+2，因为对于长度为5的小段而言，切成3+2肯定是更优解（在X = 5时已经验证过了)。但为了使得切割数量尽可能小，会选择7 = 3+4而不是7 = 3+2+2。

上述过程可以用动态规划完成，或者用数学归纳法严格证明。

但对于本题而言，贪心地找规律已经完全足够了。

PS：本题还可以延展开来思考

1. 如果本题只要求计算最大总收益，是否可以使用动态规划来完成？
2. 如果本题要求分割次数不能超过m，那么应该如何完成？是否可以使用动态规划来完成？

代码

Python

# 题目：【贪心】2023C-伐木工
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：贪心，数学
# 代码看不懂的地方，请直接在群上提问


X = int(input())
# 分类讨论
if X <= 4:
    print(X)
else:
    if X % 3 == 0:
        ans = [3] * (X // 3)
    elif X % 3 == 2:
        ans = [2] + [3] * (X // 3)
    elif X % 3 == 1:
        ans = [3] * (X // 3 - 1) + [4]
    # 解包写法，等价于
    # print(" ".join(str(i) for i in ans))
    print(*ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int X = scanner.nextInt();
        scanner.close();

        if (X <= 4) {
            System.out.println(X);
        } else {
            if (X % 3 == 0) {
                int num = X / 3;
                for (int i = 0; i < num; i++) {
                    System.out.print("3 ");
                }
            } else if (X % 3 == 2) {
                System.out.print("2 ");
                int num = X / 3;
                for (int i = 0; i < num; i++) {
                    System.out.print("3 ");
                }
            } else if (X % 3 == 1) {
                int num = X / 3 - 1;
                for (int i = 0; i < num; i++) {
                    System.out.print("3 ");
                }
                System.out.print("4");
            }
        }
    }
}

C++

“`C++
#include <iostream>
using namespace std;

int main() {
int X;
cin >> X;

<pre><code>if (X <= 4) {
cout << X;
} else {
if (X % 3 == 0) {
int num = X / 3;
for (int i = 0; i < num; i++) {
cout << "3 ";
}
} else if (X % 3 == 2) {
cout << "2 ";
int num = X / 3;
for (int i = 0; i < num; i++) {
cout << "3 ";
}
} else if (X % 3 == 1) {
int num = X / 3 – 1;
for (int i = 0; i < num; i++) {
cout << "3 ";
}
cout << "4";
}
}

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(1)。

空间复杂度：O(1)。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）

abc123算法训练营永久会员

收藏 海报 链接