【不定滑窗】2023Q1A-区块链文件转储系统

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3202

题目描述

区块链底层存储是一个链式文件系统，由顺序的 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

1000
100 500 400 150 500 100

输出

说明

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

解题思路

滑窗三问

**Q1：**对于每一个右指针right所指的元素num，做什么操作？

Q2：什么时候要令左指针left右移？left对应的元素做什么操作？while中的循环不变量是什么？

**Q3：**什么时候进行ans的更新？

滑窗三答

**A1：**将num计入窗口之和win_sum中。

A2：win_sum > M，win_sum减去left_num，left右移，直到win_sum <= M成立。

A3：win_sum <= M时，可以更新答案，可能发生在left右移之后。

代码

Python

# 题目：2023Q1A-区块链文件转储系统
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：不定滑窗
# 代码看不懂的地方，请直接在群上提问


M = int(input())
lst = list(map(int, input().split()))

ans = 0
win_sum = 0
left = 0

for right, num in enumerate(lst):
    # A1
    win_sum += num
    # A2
    while win_sum > M:
        win_sum -= lst[left]
        left += 1
    # A3
    ans = max(ans, win_sum)

print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = Integer.parseInt(scanner.nextLine());
        String[] input = scanner.nextLine().split(" ");
        int[] lst = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            lst[i] = Integer.parseInt(input[i]);
        }

        int ans = 0;
        int winSum = 0;
        int left = 0;

        for (int right = 0; right < lst.length; right++) {
            // A1
            winSum += lst[right];
            // A2
            while (winSum > M) {
                winSum -= lst[left];
                left++;
            }
            // A3
            ans = Math.max(ans, winSum);
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int M;
    cin >> M;
    vector<int> lst(M);
    for (int i = 0; i < M; i++) {
        cin >> lst[i];
    }

    int ans = 0;
    int win_sum = 0;
    int left = 0;

    for (int right = 0; right < M; right++) {
        // A1
        win_sum += lst[right];
        // A2
        while (win_sum > M) {
            win_sum -= lst[left];
            left++;
        }
        // A3
        ans = max(ans, win_sum);
    }

    cout << ans << endl;

    return 0;
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组。

空间复杂度：O(1)。仅需若干常数变量。