最新华为OD机试真题-伐木工(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎在线评测链接

=> 伐木工(200分) <=

🌍 评测功能需要订阅专栏后私信联系清隆解锁～

华为OD

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

alt

🪵 伐木工

题目描述

K小姐是一位伐木工人，她有一根长度为 米的原木。为了获得最大的收益，她需要将原木切割成若干段，每一段的长度都必须是正整数。

木材交易价格为每根木头长度的乘积，也可以不切割，拿整根原木进行交易，其交易价格等于原木长度。

现在，请你帮助K小姐计算，要想获得最大收益，并且切割次数尽量少，她应该如何切割这根原木？

输入格式

输入仅一行，包含一个正整数 ，表示原木的长度。

输出格式

输出若干个正整数，表示切割后每一段木材的长度。你需要按照长度从小到大的顺序输出，相邻两个数之间用一个空格隔开。

如果有多种切割方案都能获得最大收益，你可以输出任意一种。

样例输入

10

样例输出

3 3 4

数据范围

题解

我们可以使用动态规划来解决这个问题。设 表示将长度为 的原木切割后能获得的最大收益。

对于一根长度为 的原木，我们可以选择不切割，此时收益为 ；也可以选择将其切割成两段，长度分别为 和 ，此时收益为 。我们需要枚举所有可能的切割方案，取其中的最大值作为 的值。

最终的答案即为 。在计算出 数组后，我们可以通过倒推的方式找到一种最优的切割方案。

时间复杂度为 ，空间复杂度为 。

参考代码

  • Python 
n = int(input())
f = [0] * (n+1)
for i in range(1, n+1):
    f[i] = i
    for j in range(1, i):
        f[i] = max(f[i], max(j*f[i-j], j*(i-j)))

res = []
m = n
while m >= 1:
    if f[m] == m:
        res.append(m)
        break
    for k in range(m-1, 0, -1):
        if k*(m-k) == f[m]:
            res.append(k)
            res.append(m-k)
            m = 0
            break
        elif k*f[m-k] == f[m]:
            res.append(k)
            m -= k
            break

res.sort()
print(*res)
  • Java 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(S

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

最新华为OD机试-E+D卷 文章被收录于专栏

本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测

全部评论
到底是乘积还是平方？
1 回复 分享
发布于 07-05 06:44 河南
评测功能需要 订阅专栏 后联系清隆解锁～
点赞 回复 分享
发布于 07-01 15:22 浙江
平方不应该是 1*1 + 9*9 > 3*3+ 3*3+4*4 吗
点赞 回复 分享
发布于 07-26 00:51 四川

相关推荐

09-23 08:58
国家开放大学 Java
点赞 评论 收藏
分享
09-23 08:56
已编辑
国家开放大学 Java
华为OD 机试卷-勾股数
题目描述如果三个正整数A、B、C&nbsp;，A²&nbsp;+&nbsp;B²&nbsp;=&nbsp;C²&nbsp;则为勾股数，如果ABC之间两两互质，即A与B，A与C，B与C均互质没有公约数，则称其为勾股数元组。请求出给定&nbsp;n&nbsp;~&nbsp;m&nbsp;范围内所有的勾股数元组。输入描述起始范围1&nbsp;&lt;&nbsp;n&nbsp;&lt;&nbsp;10000n&nbsp;&lt;&nbsp;m&nbsp;&lt;&nbsp;10000输出描述ABC保证A&nbsp;&lt;&nbsp;B&nbsp;&lt;&nbsp;C输出格式A&nbsp;B&nbsp;C多组勾股数元组，按照A&nbsp;B&nbsp;C升序的排序方式输出。若给定范围内，找不到勾股数元组时，输出Na。import&nbsp;java.util.Scanner;public&nbsp;class&nbsp;Main&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;void&nbsp;main(String[]&nbsp;args)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Scanner&nbsp;in&nbsp;=&nbsp;new&nbsp;Scanner(System.in);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(in.hasNextInt())&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;n&nbsp;=&nbsp;in.nextInt();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;m&nbsp;=&nbsp;in.nextInt();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;boolean&nbsp;found&nbsp;=&nbsp;false;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;n;&nbsp;i&nbsp;&lt;=&nbsp;m;&nbsp;i++)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;j&nbsp;=&nbsp;i&nbsp;+&nbsp;1;&nbsp;j&nbsp;&lt;=&nbsp;m;&nbsp;j++)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;k&nbsp;=&nbsp;(int)&nbsp;Math.sqrt(i&nbsp;*&nbsp;i&nbsp;+&nbsp;j&nbsp;*&nbsp;j);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(k&nbsp;&gt;&nbsp;m)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(k&nbsp;*&nbsp;k&nbsp;==&nbsp;i&nbsp;*&nbsp;i&nbsp;+&nbsp;j&nbsp;*&nbsp;j)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(gcd(i,&nbsp;j)&nbsp;==&nbsp;1&nbsp;&amp;amp;&amp;amp;&nbsp;gcd(j,&nbsp;k)&nbsp;==&nbsp;1)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.printf(&amp;quot;%d&nbsp;%d&nbsp;%d\\n&amp;quot;,&nbsp;i,&nbsp;j,&nbsp;k);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;found&nbsp;=&nbsp;true;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!found)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(&amp;quot;Na&amp;quot;);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;int&nbsp;gcd(int&nbsp;a,&nbsp;int&nbsp;b)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;b&nbsp;==&nbsp;0&nbsp;?&nbsp;a&nbsp;:&nbsp;gcd(b,&nbsp;a&nbsp;%&nbsp;b);&nbsp;&nbsp;&nbsp;&nbsp;}}
投递华为等公司10个岗位
点赞 评论 收藏
分享
09-23 11:15
已编辑
无锡高等师范学校 算法工程师
华为OD机试E卷 - 最长连续子序列 Java
题目描述&nbsp;有N个正整数组成的一个序列。给定整数sum，求长度最长的连续[子序列]，使他们的和等于sum，返回此子序列的长度，&nbsp;如果没有满足要求的序列，返回-1。&nbsp;输入描述&nbsp;第一行输入是：N个正整数组成的一个序列&nbsp;第二行输入是：给定整数sum&nbsp;输出描述&nbsp;最长的连续子序列的长度&nbsp;备注&nbsp;输入序列仅由数字和英文逗号构成，数字之间采用英文逗号分隔&nbsp;序列长度：1&nbsp;&lt;=&nbsp;N&nbsp;&lt;=&nbsp;200&nbsp;输入序列不考虑异常情况&nbsp;示例1&nbsp;输入&nbsp;1,2,3,4,2&nbsp;6&nbsp;输出&nbsp;3&nbsp;说明&nbsp;1,2,3和4,2两个序列均能满足要求，所以最长的连续序列为1,2,3，因此结果为3。&nbsp;示例2&nbsp;输入&nbsp;1,2,3,4,2...
投递华为等公司10个岗位 > 2024华为OD机试E卷...
点赞 评论 收藏
分享
09-23 21:12
重庆邮电大学 C++
点赞 评论 收藏
分享
09-23 15:50
西安邮电大学 Java
点赞 评论 收藏
分享
1 4 评论
分享

招聘动态

查看更多

产险科技

2025校园招聘

阿里云管培生

2025届校园招聘

北京农商银行25届校招

招商银行上海分行

2025校园招聘

25届销售专场

秋招留学生专场开启啦

25届智能制造专场

建信金科

2025届秋季校招

2025届红杉联合校招

平安产险总部科技中心

全站热榜

正在热议
# 实习与准备秋招该如何平衡 #
568063次浏览 7137人参与
# 你的简历改到第几版了 #
591858次浏览 8819人参与
# 欧莱雅秋招 #
17560次浏览 201人参与
# 国央企求职进展汇总 #
19023次浏览 86人参与
# 国庆前的秋招小结 #
17987次浏览 267人参与
# 比亚迪求职进展汇总 #
370054次浏览 2059人参与
# 广发卡校招来了 #
723次浏览 6人参与
# 互联网公司评价 #
230681次浏览 2946人参与
# 选完offer后，你后悔学机械吗？ #
8037次浏览 54人参与
# 秋招OC许愿 #
4457次浏览 177人参与
# 硬件人的简历怎么写 #
189419次浏览 2485人参与
# 找工作，你会甘心进小厂还是猛冲大厂 #
78470次浏览 687人参与
# 银行笔面经互助 #
8398次浏览 130人参与
# 在职场上，你最讨厌什么样的同事 #
3519次浏览 52人参与
# 实习工作，你找得还顺利吗？ #
219059次浏览 2456人参与
# 0offer互助地 #
109444次浏览 1158人参与
# 你的国庆怎么过 #
10725次浏览 166人参与
# 投递实习岗位前的准备 #
1051316次浏览 16938人参与
# 同事是个抢功怪怎么办 #
16332次浏览 115人参与
# 牛友的志愿填报指南 #
15721次浏览 146人参与
# 工作后明白的那些道理 #
9428次浏览 163人参与
# 秋招开了，你想投哪些公司呢 #
485260次浏览 8533人参与
牛客网
牛客企业服务