当前位置：首页 > news >正文

【华为OD机试真题】伐木工 · 木材切割收益最大化问题（C语言）

news 2026/5/11 23:59:04

一、题目

题目描述：
一根X米长的树木，伐木工切割成不同长度的木材后进行交易，交易价格为每根木头长度的乘积。规定切割后的每根木头长度都为正整数，也可以不切割，直接拿整根树木进行交易。请问伐木工如何尽量少的切割，才能使收益最大化？
输入描述:
木材的长度(X<=50)
输出描述:
输出最优收益时的各个树木长度，以空格分割，按升序排列
示例1
输入:
10
输出:
3 3 4
说明:
一根2米长的树木，伐木工不切割，为21，收益最大为2
一根4米长的树木，伐木工不需要切割为22，省去切割成本，直接整根树木交易，为41，收益最大为4
一根5米长的树木，伐木工切割为23，收益最大为 6
一根10米长的树木，伐木工可以切割为方式: 3, 4, 3，也可以切割为方式二: 3, 2, 2, 3，但方式二伐木工多切割了一次增加切割成本却卖了一样的价格，因此并不是最优收益。

二、题目分析与解题思路🧠

这道题本质上是经典的整数拆分问题的变种，核心在于通过数学规律找到贪心策略。

1. 核心数学规律推导

我们要把 n 拆分成 a1+a2+...+ak ，使得 P=a1×a2×...×ak 最大。

避免长度为 1：任何数乘以 1 都不会变大（1×n=n ），反而浪费长度，所以因子中不能有 1。
优先切分为 3：
- 当 n≥5 时，我们可以证明 3(n−3)>n 。
- 例如：5→2+3(6>5) ，6→3+3(9>6) 。
- 这意味着，只要长度大于等于 5，我们就应该把它切分，且切出一个 3 是最优的。
关于 4 的处理：
- 4 可以拆成 2+2 ，乘积 2×2=4 ，与原值相等。
- 关键点：题目要求“尽量少切割”。既然 44 切割后收益不增，我们选择保留 4 不切（或者理解为拆成 2+2 后，在输出时合并）。
- 注意：在纯数学的“整数拆分”题中，通常 4 会被视为 2+2，但本题有“最少切割”约束，且 2×2=4 ，所以保留 4 或拆成 2,2 对乘积无影响，但对切割次数有影响。但在贪心策略中，当剩余长度为 4 时，直接保留即可。

2. 贪心算法步骤

特殊情况：若 X≤4 ，直接输出 X （因为切割不会增加收益，反而增加成本）。
循环切分：当 X>4 时，不断切出长度为3的段，直到剩余长度 ≤4 。
处理剩余：将剩余的长度（可能是 2, 3, 或 4）作为最后一段加入结果。
排序输出：题目要求升序排列。由于我们先切出的是 3，最后剩下的可能是 2、3 或 4，为了保证绝对升序（例如 2 在 3 前面），建议使用排序或简单的逻辑判断。

三、C语言实现🚀

C语言实现如下：

#include <stdio.h> #include <stdlib.h> // 定义最大可能的段数，X<=50，全切成2也就25段，50足够安全 #define MAX_SEGMENTS 50 // 比较函数，用于qsort升序排列 int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b); } int main() { int X; // 读取输入 if (scanf("%d", &X) != 1) { return 0; } int segments[MAX_SEGMENTS]; int count = 0; // 1. 特殊情况处理：X <= 4 时，切割不会增加收益，且会增加切割成本 if (X <= 4) { printf("%d\n", X); return 0; } // 2. 贪心策略：只要长度大于4，就优先切出长度为3的段 // 原理：3*(X-3) > X (当X>=5时) while (X > 4) { segments[count++] = 3; X -= 3; } // 3. 处理剩余部分（此时 X 必然是 2, 3 或 4） // 注意：如果是4，保留为4（相当于2+2但不切），符合“最少切割”原则 if (X > 0) { segments[count++] = X; } // 4. 题目要求升序排列，使用qsort进行排序 // 虽然贪心逻辑下通常已经是 3...3, (2|3|4)，但为了代码健壮性建议排序 qsort(segments, count, sizeof(int), compare); // 5. 输出结果 for (int i = 0; i < count; i++) { if (i > 0) { printf(" "); } printf("%d", segments[i]); } printf("\n"); return 0; }

代码说明与复杂度分析

输入处理：使用scanf读取木材长度 X 。
贪心循环：当 X>4 时，循环减去 3 并记录段长。这是基于数学推导的最优解。
剩余处理：循环结束后，若 X>0 ，将其作为最后一段。此时 X 只可能是 2、3 或 4。
排序：虽然按照贪心逻辑（先切3，剩4），结果通常是3, 3, 4或3, 2。为了满足题目严格的“升序排列”要求（例如2, 3），代码中加入了qsort。
- 注：如果不使用 qsort，也可以通过逻辑判断手动调整 2 和 3 的顺序，但在机考中直接排序最稳妥。
输出：遍历数组，以空格分隔输出。