2023年华为OD机考真题：区块链文件转储系统

算法刷题1年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：区块链文件转储系统
知识点栈链表单调栈滑窗
时间限制：2s 空间限制：256MB 限定语言：不限
题目描述：
区块链底层存储是一个链式文件系统，由顺序的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]
解题思路：
使用滑窗来求得连续文件大小和的最大值。
如示例2：

代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 区块链文件转储系统
 * @Description 区块链底层存储是一个链式文件系统，由顺序的N个文件组成，每个文件的大小不一，依次为F1,F2...Fn。随着时间的推移，所占存储会越来越大。
 * 云平台考虑将区块链按文件转储到廉价的SATA盘，只有连续的区块链文件才能转储到SATA盘上，且转储的文件之和不能超过SATA盘的容量。
 * 假设每块SATA盘容量为M，求能转储的最大连续文件大小之和。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        sc.nextLine();
        String[] strings = sc.nextLine().split(" ");
        int left = 0;   //滑窗左边界
        int right = 1;  //滑窗右边界
        int count = Integer.parseInt(strings[0]);    //连续文件大小之和
        int max = 0;    //最大连续和
        while (max != M && (right < strings.length || count > max)) {  //当max==M时直接图退出，当右边界到头且count小于max时退出
            if (count <= M) {
                max = Math.max(max, count);
                if (right < strings.length) {     //控制滑窗右边界
                    count += Integer.parseInt(strings[right]);
                    right++;
                }
            } else {
                count -= Integer.parseInt(strings[left]);
                left++;
            }
        }
        System.out.println(max);
    }
}

代码实现二：Java代码满分实现

package com.codernav.demo.hwod.exam;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @title 区块链文件转储系统
 * @Description 区块链底层存储是一个链式文件系统，由顺序的N个文件组成，每个文件的大小不一，依次为F1,F2...Fn。随着时间的推移，所占存储会越来越大。
 * 云平台考虑将区块链按文件转储到廉价的SATA盘，只有连续的区块链文件才能转储到SATA盘上，且转储的文件之和不能超过SATA盘的容量。
 * 假设每块SATA盘容量为M，求能转储的最大连续文件大小之和。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        int res = 0;
        Scanner in = new Scanner(System.in);
        int sataSize = in.nextInt();
        List<Integer> fileSizeList = new ArrayList<>();
        while (in.hasNext()) {
            fileSizeList.add(in.nextInt());
        }
        int sum = 0;
        int fast = 0, slow = 0;
        while (fast < fileSizeList.size()) {
            sum += fileSizeList.get(fast);
            while (sum > sataSize) {
                sum -= fileSizeList.get(slow);
                slow++;
            }
            if (sum > res) {
                res = sum;
            }
            fast++;
        }
        System.out.println(res);
    }
}