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

_JeanW_

342人浏览 · 2026-03-26 20:21:55

_JeanW_ · 2026-03-26 20:21:55 发布

一、题目

题目描述：
一根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. 核心数学规律推导

我们要把 nn 拆分成 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 ，与原值相等。
- 关键点：题目要求“尽量少切割”。既然 4 切割后收益不增，我们选择保留 4 不切（或者理解为拆成 2+2 后，在输出时合并）。
- 注意：在纯数学的“整数拆分”题中，通常 4 会被视为 2+2 ，但本题有“最少切割”约束，且 2×2=4 ，所以保留 4或拆成 2,2 对乘积无影响，但对切割次数有影响。但在贪心策略中，当剩余长度为 4 时，直接保留即可。

2. 贪心算法步骤

特殊情况：若 X≤4 ，直接输出 X （因为切割不会增加收益，反而增加成本）。
循环切分：当 X>4 时，不断切出长度为 3 的段，直到剩余长度 ≤4 。
处理剩余：将剩余的长度（可能是 2, 3, 或 4）作为最后一段加入结果。
排序输出：题目要求升序排列。

三、Java 实现🚀

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class WoodCutting {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        if (scanner.hasNext()) {
            int X = scanner.nextInt();
            List<Integer> result = new ArrayList<>();

            // 1. 处理特殊情况：X <= 4 时，切割不会增加收益，且会增加切割成本
            if (X <= 4) {
                System.out.println(X);
                return;
            }

            // 2. 贪心策略：只要长度大于4，就优先切出长度为3的段
            // 因为 3*(X-3) > X (当X>=5时)
            while (X > 4) {
                result.add(3);
                X -= 3;
            }

            // 3. 处理剩余部分（此时 X 必然是 2, 3 或 4）
            // 注意：如果是4，保留为4（相当于2+2但不切），符合“最少切割”原则
            if (X > 0) {
                result.add(X);
            }

            // 4. 升序排序并输出
            Collections.sort(result);
            for (int i = 0; i < result.size(); i++) {
                System.out.print(result.get(i));
                if (i < result.size() - 1) {
                    System.out.print(" ");
                }
            }
        }
        scanner.close();
    }
}

四、Go 实现🚀

package main

import (
    "fmt"
    "sort"
)

func main() {
    var X int
    fmt.Scan(&X)
    var result []int

    // 1. 特殊情况处理
    if X <= 4 {
        fmt.Println(X)
        return
    }

    // 2. 贪心切分：优先切出 3
    for X > 4 {
        result = append(result, 3)
        X -= 3
    }

    // 3. 处理剩余长度
    if X > 0 {
        result = append(result, X)
    }

    // 4. 排序输出
    sort.Ints(result)
    for i, v := range result {
        fmt.Print(v)
        if i < len(result)-1 {
            fmt.Print(" ")
        }
    }
}