一根X米长的树木，伐木工切割成不同长度的木材后进行交易，交易价格为每根木头长度的乘积。
规定切割后的每根木头长度都为正整数，也可以不切割，直接拿整根树木进行交易。
请问伐木工如何尽量少的切割，才能使收益最大化？
木材的长度 (X<=50)
输出最优收益时的各个树木长度，以空格分割，按升序排列
10
3 3 4
从1开始枚举树木长度X，寻找规律。
树木长度X | 最优分组 | 最大总收益 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 3 | 3 |
| 4 | 4 | 4 |
| 5 | 3 2 | 6 |
| 6 | 3 3 | 9 |
| 7 | 3 4 | 12 |
| 8 | 3 3 2 | 18 |
| 9 | 3 3 3 | 27 |
| 10 | 3 3 4 | 36 |
| 11 | 3 3 3 2 | 54 |
| 12 | 3 3 3 3 | 81 |
| 13 | 3 3 3 4 | 108 |
| … | … | … |
容易观察得出规律。
3的小段，这样才能使得乘积的收益尽可能大。X <= 4时，不进行切割。注意4不会被切割为2 2，因为虽然2 2也能得到4的总收益，但是并不是切割数最小的方式X > 4且X % 3 == 0时，分成n // 3组长度为3的小段。X > 4且X % 3 == 2时，分成n // 3组长度为3的小段，1组长度为2的小段。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：本题还可以延展开来思考
m，那么应该如何完成？是否可以使用动态规划来完成？# 题目：【贪心】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)
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");
}
}
}
}
#include <iostream>
using namespace std;
int main() {
int X;
cin >> X;
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;
}
时间复杂度：O(1)。
空间复杂度：O(1)。
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接 大厂真题汇总 & OD真题汇总(持续更新)
绿色聊天软件戳 od1336了解更多