您现在的位置是：首页 >技术教程 >2023华为OD机试真题【区块链转储系统】网站首页技术教程

题目描述

区块链底层存储是一个链式文件系统，由顺序的N个文件组成，每个文件的大小不一，依次为F1.F2…Fn。随着时间的推移，所占存储会越来越大。
云平台考虑将区块链按文件转储到廉价的SATA盘，只有连续的区块链文件才能转储到SATA盘上，且转的文件之和不能超过SATA盘的容量。
假设每块SATA盘容量为M，求能转储的最大连续文件之和。
输入描述
第一行为SATA盘容量M，1000 <= M <= 1000000
第二行为区块链文件大小序列F1,F2,…,Fn。其中 1<= n <=100000，1<= Fis <= 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]

解题思路

使用滑动窗口来解题。通过遍历文件大小数组（比如示例1中的【100 300 500 400 400 150 100】），不断调整窗口左右边界，使得窗口和尽可能接近磁盘容量。

在每次迭代中，首先计算加上右边界文件大小后的窗口和。此时有3中情况：

1.如果大于磁盘容量，则减去左边界的文件大小，并将左边界向右移动一位；
2.如果小于磁盘容量，将右边界的文件大小加入窗口和，并更新最大窗口和；
3.如果等于磁盘容量，则直接输出磁盘容量并返回。

最后，输出最大窗口和作为答案。

参考代码

配套视频讲解：https://www.bilibili.com/video/BV18s4y117pM

import java.util.Scanner;
import java.util.Arrays;

class Main {
    public static void main(String[] args) {
        // 获取输入
        Scanner in = new Scanner(System.in);
        int diskCapacity = in.nextInt();
        in.nextLine();
        Integer[] fileSizes = Arrays.stream(in.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

        // 初始化窗口左右边界、窗口和、最大窗口和
        int left = 0, right = 0;
        int windowSum = 0;
        int maxWindowSum = 0;

        while (right < fileSizes.length) {
            int temp = windowSum + fileSizes[right];

            // 如果窗口和大于磁盘容量，减去左边界的文件大小，左边界向右移动一位
            if (temp > diskCapacity) {
                windowSum -= fileSizes[left];
                left += 1;
            }
            // 如果窗口和小于磁盘容量，右边界向右移动一位，增加右边界的文件大小
            else if (temp < diskCapacity) {
                windowSum += fileSizes[right];
                maxWindowSum = Math.max(windowSum, maxWindowSum);
                right += 1;
            }
            // 如果窗口和等于磁盘容量，输出磁盘容量并返回
            else {
                System.out.println(diskCapacity);
                return;
            }
        }

        System.out.println(maxWindowSum);
    }
}

动态规划解法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int diskCapacity = in.nextInt();
        int n = in.nextInt();
        int[] fileSizes = new int[n];
        for (int i = 0; i < n; i++) {
            fileSizes[i] = in.nextInt();
        }

        // 初始化动态规划数组 dp，其中 dp[i] 表示在容量为 i 的情况下，最接近并且不超过磁盘容量的连续文件大小之和
        int[] dp = new int[diskCapacity + 1];

        // 遍历文件大小序列
        for (int i = 0; i < n; i++) {
            // 从后往前遍历 dp 数组，将当前文件大小加入到已有的子序列中
            for (int j = diskCapacity; j >= fileSizes[i]; j--) {
                // 更新 dp 数组，使 dp[j] 保持最大值
                dp[j] = Math.max(dp[j], dp[j - fileSizes[i]] + fileSizes[i]);
            }
        }
        System.out.println(dp[diskCapacity]);
    }
}