文章目录
- 【华为OD】区块链文件转储系统
-
- 题目描述
- 输入描述
- 输出描述
- 示例
-
- 示例一
- 示例二
- 解题思路
- 解法一：滑动窗口法
-
- Java实现
- Python实现
- C++实现
- 解法二：暴力枚举法
-
- Java实现
- Python实现
- C++实现
- 算法分析
-
- 时间复杂度
- 空间复杂度
- 推荐方案
- 总结
【华为OD】区块链文件转储系统
题目描述
区块链底层存储是一个链式文件系统，由顺序的 N 个文件组成，每个文件的大小不一，依次为F1,F2,…,Fn。随着时间的推移，所占存储会越来越大，云平台考虑将区块链按文件转储到廉价的SATA 盘，只有连续的区块链文件才能转储到 SATA盘上，且转储的文件之和不能超过SATA 盘的容量。假设每块 SATA 盘容量为 M，求能转储的最大连续文件大小之和。
输入描述
第一行为 SATA 盘容量 M，1000 ≤ M ≤ 1000000 第二行为区块链文件大小序列 F1, F2, …, Fn。其中 1 ≤ n ≤ 100000，1 ≤ Fi ≤ 500
输出描述
求能转储的最大连续文件大小之和。
示例
示例一
输入：
1000
100 300 500 400 400 150 100
输出：
950
说明： 最大序列和为 950，序列为 [400, 400, 150]
示例二
输入：
1000
100 500 400 150 500 100
输出：
1000
说明： 最大序列和为 1000，序列为 [100, 500, 400]
解题思路
这是一个经典的最大连续子数组和问题的变种，需要在满足和不超过容量M的约束条件下，找到最大的连续子数组和。
我们可以使用两种方法来解决：
解法一：滑动窗口法
滑动窗口是解决这类问题的最优方法，时间复杂度为O(n)。
Java实现
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int M = scanner.nextInt();
scanner.nextLine(); // 消费换行符
String[] fileStr = scanner.nextLine().split(" ");
int[] files = new int[fileStr.length];
for (int i = 0; i < fileStr.length; i++) {
files[i] = Integer.parseInt(fileStr[i]);
}
int maxSum = 0;
int left = 0;
int currentSum = 0;
for (int right = 0; right < files.length; right++) {
currentSum += files[right];
// 如果当前和超过容量，收缩左边界
while (currentSum > M && left <= right) {
currentSum -= files[left];
left++;
}
// 更新最大和
maxSum = Math.max(maxSum, currentSum);
}
System.out.println(maxSum);
}
}
Python实现
def solve():
M = int(input())
files = list(map(int, input().split()))
max_sum = 0
left = 0
current_sum = 0
for right in range(len(files)):
current_sum += files[right]
# 如果当前和超过容量，收缩左边界
while current_sum > M and left <= right:
current_sum -= files[left]
left += 1
# 更新最大和
max_sum = max(max_sum, current_sum)
print(max_sum)
solve()
C++实现
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;
int main() {
int M;
cin >> M;
cin.ignore(); // 忽略换行符
string line;
getline(cin, line);
istringstream iss(line);
vector<int> files;
int file;
while (iss >> file) {
files.push_back(file);
}
int maxSum = 0;
int left = 0;
int currentSum = 0;
for (int right = 0; right < files.size(); right++) {
currentSum += files[right];
// 如果当前和超过容量，收缩左边界
while (currentSum > M && left <= right) {
currentSum -= files[left];
left++;
}
// 更新最大和
maxSum = max(maxSum, currentSum);
}
cout << maxSum << endl;
return 0;
}
解法二：暴力枚举法
虽然时间复杂度较高O(n²)，但思路简单直观，适合理解问题本质。
Java实现
import java.util.*;
public class Solution2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int M = scanner.nextInt();
scanner.nextLine();
String[] fileStr = scanner.nextLine().split(" ");
int[] files = new int[fileStr.length];
for (int i = 0; i < fileStr.length; i++) {
files[i] = Integer.parseInt(fileStr[i]);
}
int maxSum = 0;
// 枚举所有可能的起始位置
for (int i = 0; i < files.length; i++) {
int currentSum = 0;
// 从起始位置开始累加
for (int j = i; j < files.length; j++) {
currentSum += files[j];
if (currentSum <= M) {
maxSum = Math.max(maxSum, currentSum);
} else {
break; // 超过容量，停止扩展
}
}
}
System.out.println(maxSum);
}
}
Python实现
def solve_brute_force():
M = int(input())
files = list(map(int, input().split()))
max_sum = 0
# 枚举所有可能的起始位置
for i in range(len(files)):
current_sum = 0
# 从起始位置开始累加
for j in range(i, len(files)):
current_sum += files[j]
if current_sum <= M:
max_sum = max(max_sum, current_sum)
else:
break # 超过容量，停止扩展
print(max_sum)
solve_brute_force()
C++实现
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;
int main() {
int M;
cin >> M;
cin.ignore();
string line;
getline(cin, line);
istringstream iss(line);
vector<int> files;
int file;
while (iss >> file) {
files.push_back(file);
}
int maxSum = 0;
// 枚举所有可能的起始位置
for (int i = 0; i < files.size(); i++) {
int currentSum = 0;
// 从起始位置开始累加
for (int j = i; j < files.size(); j++) {
currentSum += files[j];
if (currentSum <= M) {
maxSum = max(maxSum, currentSum);
} else {
break; // 超过容量，停止扩展
}
}
}
cout << maxSum << endl;
return 0;
}
算法分析
时间复杂度
- 滑动窗口法：O(n)，每个元素最多被访问两次
- 暴力枚举法：O(n²)，需要枚举所有可能的子数组
空间复杂度
- 两种方法的空间复杂度都是O(n)，主要用于存储输入数组
推荐方案
对于本题的数据规模（n ≤ 100000），强烈推荐使用滑动窗口法，因为：
总结
区块链文件转储系统问题本质上是一个约束条件下的最大连续子数组和问题。通过滑动窗口技术，我们可以高效地解决这个问题。这种方法在处理连续子数组相关问题时非常有用，是算法面试中的常考知识点。
