【最新华为OD机试E卷】通过软盘拷贝文件(200分)
🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员
💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历
✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸
最新华为OD机试E卷目录，全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目敬请期待
最新华为OD机试目录: https://www.nowcoder.com/share/jump/3022116661724989756887
🎀关于华为OD
- ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
- ⌚️华为 OD 应聘流程
-
第一步：投递简历
- 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。
-
第二步：机试
- 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。
-
第三步：技术面
- 2 轮技术面试。
-
第四步：HR 与主管面试
-
第五步：录用，发 offer
-
🍓OJ题目截图
💿 通过软盘拷贝文件
问题描述
一位科学家正在研究一台古董电脑中的文件。这台电脑只有一个 3.5 寸软盘驱动器可以用来拷贝文件,而且只有一张软盘可用。科学家希望能够最大化地利用这张软盘,将尽可能多的文件内容拷贝出来。
已知:
- 软盘容量为 1474560 字节。
- 文件在软盘上按块分配空间,每块大小为 512 字节。
- 一个块只能被一个文件使用。
- 拷贝到软盘中的文件必须是完整的,不能采取任何压缩技术。
- 为了充分利用软盘空间,文件在软盘上实际占用的块数会被记录下来,不计入软盘使用空间。
科学家的目标是使拷贝到软盘中的文件内容总大小最大。请你帮助科学家计算出能够拷贝的最大文件总大小。
输入格式
第一行包含一个整数 ,表示计算机中的文件数量。
。
接下来 行,每行包含一个整数
,表示第
个文件的大小(单位:字节)。
。
输出格式
输出一个整数,表示科学家最多能拷贝的文件总大小(单位:字节)。
样例输入
3
737270
737272
737288
样例输出
1474542
样例解释
3 个文件中,每个文件实际占用的大小分别为 737280 字节、737280 字节、737792 字节。只能选取前两个文件,总大小为 1474542 字节。虽然后两个文件总大小更大且未超过 1474560 字节,但因为实际占用的大小超过了 1474560 字节,所以不能选后两个文件。
样例输入
6
400000
200000
200000
200000
400000
400000
样例输出
1400000
样例解释
从 6 个文件中,选择 3 个大小为 400000 的文件和 1 个大小为 200000 的文件,得到最大总大小为 1400000。也可以选择 2 个大小为 400000 的文件和 3 个大小为 200000 的文件,得到的总大小也是 1400000。
数据范围
题解
这道题目本质上是一个变形的 0-1 背包问题。
需要从给定的文件中选择一些,使得它们的总大小不超过软盘容量,同时尽可能地大。
关键点在于理解文件在软盘上的存储方式。每个文件占用的空间都是 512 字节的整数倍，但我们只需要考虑文件的实际大小。
这意味着我们可以直接使用文件的原始大小进行计算,而不需要考虑向上取整到 512 的倍数。
解题步骤:
- 读入所有文件的大小。
- 创建一个动态规划数组 dp,其中 dp[i] 表示容量为 i 时可以存储的最大文件总大小。
- 遍历每个文件,对于每个文件,更新 dp 数组。
- 最终 dp[1474560 / 512] 就是我们要求的答案。
- Python
# 读取输入
n = int(input()) # 文件数量
files = [int(input()) for _ in range(n)] # 每个文件的大小
# 软盘容量（以块为单位）
CAPACITY = 1474560 // 512
# 创建动态规划数组
dp = [0] * (CAPACITY + 1)
# 动态规划过程
for file in files:
# 计算文件占用的块数
blocks = (file + 511) // 512
# 从大到小遍历容量,避免重复计算
for i in range(CAPACITY, blocks - 1, -1):
# 选择不拷贝该文件或拷贝该文件,取较大值
dp[i] = 剩余60%内容，订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测
查看9道真题和解析
投递华为等公司10个岗位 >