2025 A卷 200分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

本文收录于专栏：《2025华为OD真题目录+全流程解析/备考攻略/经验分享》

华为OD机试真题《通过软盘拷贝文件》：

---

---

题目名称：通过软盘拷贝文件

---

• 知识点：动态规划（01背包）
• 时间限制：1秒
• 空间限制：256MB
• 限定语言：不限

---

题目描述

科学家需要从古董电脑中拷贝文件到软盘，软盘容量为 1474560 字节。文件存储按块分配，每个块 512 字节，一个块只能被一个文件占用。文件必须完整拷贝且不压缩。目标是使软盘中文件总大小最大。

输入描述

• 第1行为整数 N，表示文件数量（1 ≤ N < 1000）。
• 第2行到第N+1行，每行为一个整数，表示文件大小 Si（单位：字节，0 < Si ≤ 1000000）。

输出描述

• 输出科学家能拷贝的最大文件总大小。

示例
输入：

3  
737270  
737272  
737288  

输出：

1474542  

说明

• 文件块计算方式：每个文件大小向上取整到512的倍数。例如737270字节占用 ceil(737270/512) = 1440 块。
• 软盘总块数为 1474560/512 = 2880 块。选择前两个文件占用 1440 + 1440 = 2880 块，总大小为 737270 + 737272 = 1474542 字节。

补充说明

• 动态规划（01背包问题）或回溯法是典型解法。文件块为背包容量，文件大小为价值，需最大化总价值。

---

Java

问题分析

我们需要在给定多个文件的情况下，选择一些文件拷贝到软盘上，使得总块数不超过软盘容量，同时总文件大小最大。每个文件的大小按512字节向上取整计算块数。这是一个典型的0-1背包问题，其中背包容量是软盘的总块数，每个文件的体积是其块数，价值是文件实际大小。

---

解题思路

1. 块数计算：对每个文件大小，计算其占用的块数（向上取整到512的倍数）。
2. 动态规划：使用动态规划求解0-1背包问题。定义dp[i]为容量i时的最大总价值。
3. 结果构造：遍历所有可能的容量，找到最大总价值。

---

代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt(); // 读取文件数量int[] sizes = new int[N]; // 存储每个文件的大小for (int i = 0; i < N; i++) {sizes[i] = scanner.nextInt();}int totalBlocks = 1474560 / 512; // 软盘总块数2880int[] dp = new int[totalBlocks + 1]; // dp数组，dp[i]表示容量i时的最大总价值for (int size : sizes) { // 遍历每个文件int blocks = (size + 511) / 512; // 计算块数：向上取整int value = size; // 价值是文件实际大小// 逆序更新dp数组，确保每个文件只选一次for (int j = totalBlocks; j >= blocks; j--) {if (dp[j - blocks] + value > dp[j]) {dp[j] = dp[j - blocks] + value;}}}// 找出dp数组中的最大值int max = 0;for (int j = 0; j <= totalBlocks; j++) {if (dp[j] > max) {max = dp[j];}}System.out.println(max);}
}

---

代码详细解析

1. 输入处理：

   • Scanner读取输入，N为文件数量，sizes数组存储每个文件的大小。

2. 块数计算：

   • 每个文件的块数通过(size + 511) / 512计算，实现向上取整。

3. 动态规划数组初始化：

   • dp数组长度为totalBlocks + 1，初始值为0。

4. 动态规划过程：

   • 对每个文件，逆序遍历容量（从totalBlocks到当前文件块数），更新dp数组。
   • 逆序更新确保每个文件仅被考虑一次，符合0-1背包要求。

5. 结果提取：

   • 遍历dp数组，找到最大值即为答案。

---

示例测试

示例1输入：

3  
737270  
737272  
737288  

输出：

1474542  

解析：

• 块数分别为1440、1440、1441。选中前两个文件，总块数2880，总价值1474542。

示例2输入：

2  
513 1023  

输出：

1023  

解析：

• 块数分别为2（513→2块）、2（1023→2块）。总块数4，容量2880远大于4。选1023。

示例3输入：

1  
1474560  

输出：

0  

解析：

• 块数2880，超过软盘容量2880？文件大小1474560正好占用2880块，总和等于容量，输出1474560？

注意：示例3可能存在错误，实际块数为1474560 /512 = 2880块。若文件大小1474560，则块数2880，总块数刚好等于容量，应输出1474560。可能需要验证题目条件。

---

综合分析

1. 时间复杂度：O(N × M)，其中N为文件数量，M为总块数（2880）。满足题目时间限制。
2. 空间复杂度：O(M)，动态规划数组仅需线性空间。
3. 优势：
   • 动态规划高效解决背包问题。
   • 块数计算准确，确保正确性。
4. 适用场景：适用于文件数量大但总块数适中的场景。

---

python

问题分析

我们需要选择若干文件拷贝到软盘上，使得总块数不超过软盘容量，同时总文件大小最大。每个文件大小需向上取整到512字节的块数。这是典型的0-1背包问题，块数为容量，文件实际大小为价值。

---

解题思路

1. 块数计算：每个文件大小向上取整到512的倍数。
2. 动态规划：使用一维数组 dp 表示容量为 i 时的最大总价值。
3. 逆序更新：确保每个文件只被选择一次。

---

代码实现

def main():import sysinput = sys.stdin.read().split()idx = 0N = int(input[idx])  # 读取文件数量idx += 1sizes = []for _ in range(N):sizes.append(int(input[idx]))  # 读取所有文件大小idx += 1total_blocks = 1474560 // 512  # 总块数2880dp = [