【华为OD机试2023】区块链文件转储系统Python

题目描述：

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

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

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

输入描述：

第一行为SATA盘容量M，1000<=M<=1000000

第二行为区块链文件大小序列F1,F2...Fn。其中 1<=n<=100000， 1<=Fi<=500

输出描述：

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

示例1

输入：

1000

100 300 500 400 400 150 100

输出：

950

说明：

最大序列和为950，序列为[400,400,150]

示例2

输入：

1000

100 500 400 150 500 100

输出：

1000

说明：

最大序列和为1000，序列为[100,500,400]

解题思路：

滑动窗口，解释着比较麻烦，牛客也不给贴链接，所以请自行找一些大佬的解释吧（带图的更容易理解）

#优化版，发现用队列来实现更加易懂和形象，至于性能就不知道了
n=int(input())
lst=list(map(int,input().split()))
l=len(lst)
queue=[]
sum=0
start=0
res=[]
while True:
    if start==l:
        break
    if sum<n:
        queue.append(lst[start])
        sum+=lst[start]
        start+=1
    else:
        sum-=queue[0]
        queue.pop(0)
    if sum<=n:
        res.append(sum)
print(max(res))

#旧版
size=int(input())
lst=list(map(int,input().split()))
l=len(lst)
i=0
j=1
count=lst[i]+lst[j]
max_num=0
while True:
    if count>size:
        if j-i==1:
            i+=1
            j+=1
            if j>l:
                break
            else:
                count=lst[i]+lst[j]
        else:
            count-=lst[i]
            i+=1
    else:
        max_num=max(max_num,count)
        j+=1
        if j >l-1:
            break
        else:
            count+=lst[j]
print(max_num)