【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【贪心】2023C-伐木工【欧弟算法】全网注释最详细分类最全的华为OD真题题解

发布时间:2023年12月28日

题目描述与示例

题目描述

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

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

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

输入描述

木材的长度 (X<=50)

输出描述

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

示例

输入

10

输出

3 3 4

解题思路

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

树木长度X最优分组最大总收益
111
222
333
444
53 26
63 39
73 412
83 3 218
93 3 327
103 3 436
113 3 3 254
123 3 3 381
133 3 3 4108

容易观察得出规律。

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

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

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

所以段数应该尽量被切成23的长度(不能切成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++

#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算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

文章来源:https://blog.csdn.net/weixin_48157259/article/details/135270084
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。