刷题笔记合集🔗

区块链文件转储系统

问题描述

区块链底层存储是一个链式文件系统，由顺序的 个文件组成，每个文件的大小不一，依次为 。随着时间的推移，所占存储会越来越大。

云平台考虑将区块链按文件转储到廉价的 SATA 盘，只有连续的区块链文件才能转储到 SATA 盘上，且转储的文件之和不能超过 SATA 盘的容量。

假设每块 SATA 盘容量为 ，求能转储的最大连续文件之和。

输入格式

第一行为 SATA 盘容量 ，。

第二行为区块链文件大小序列 。其中 ，。

输出格式

求能转储的最大连续文件大小之和。

样例输入

1000
100 300 500 400 400 150 100

1000
100 500 400 150 500 100

样例输出

950

1000

数据范围

题解

这道题目本质上是求满足某个条件的最大连续子数组和，关键是找到适合的算法思路。

在本题中，我们需要在区块链文件序列中找到一个连续的子序列，使得其和最大，且不超过 SATA 盘的容量 M。这个问题可以使用滑动窗口（双指针）算法高效解决。

滑动窗口方法的基本思路是：维护一个可变大小的"窗口"，这个窗口表示当前考虑的连续子序列。通过移动窗口的左右边界，我们可以在线性时间内找到满足条件的最大子数组和。

具体步骤如下：

1. 使用两个指针 left 和 right 分别表示窗口的左右边界
2. 维护一个变量 sum 表示当前窗口内所有元素的和
3. 维护一个变量 max_sum 表示目前为止找到的最大和

滑动窗口的移动规则：

• 如果当前窗口内的和小于等于容量 M，那么尝试扩大窗口（right++），同时更新 max_sum
• 如果当前窗口内的和大于容量 M，那么缩小窗口（left++）
• 如果当前窗口内的和恰好等于容量 M，那么已经找到最优解，直接返回 M

实现时需要注意几个边界情况：

• 初始时 left 和 right 都指向第一个元素
• 当 right 到达数组末尾时，结束算法
• 每次更新窗口后，都要检查当前和是否为新的最大值

时间复杂度分析：算法只需要遍历一次数组，每个元素最多被左右指针各访问一次，因此时间复杂度为 O(n)，其中 n 是区块链文件的数量。这对于题目给出的数据范围（n ≤ 100000）是完全可接受的。

空间复杂度为 O(1)，因为我们只需要常数级的额外空间来存储变量。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取SATA盘容量M
m = int(input())
# 读取区块链文件大小序列
files = list(map(int, input().split()))

# 使用滑动窗口法求解最大连续子数组和
def find_max_subarray(arr, cap):
    """
    查找不超过容量cap的最大连续子数组和
    
    参数:
        arr: 区块链文件大小列表
        cap: SATA盘容量
        
    返回:
        最大连续子数组和
    """
    # 初始化双指针与变量
    left = 0
    curr_sum = 0
    max_sum = 0
    
    # 右指针遍历整个数组
    for right in range(len(arr)):
        # 增加当前文件大小
        curr_sum += arr[right]
        
        # 当总和超过容量时，移动左指针缩小窗口
        while curr_sum > cap and left <= right:
            curr_sum -= arr[left]
            left += 1
        
        # 更新最大和
        ma