一、题目描述

区块链底层存储是一个链式文件系统，由顺序的N个文件组成，每个文件的大小不一，依次为F1,F2…Fn。

随着时间的推移，所占存储会越来越大。

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

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

二、输入描述

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

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

三、输出描述

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

四、解题思路

  1. 使用双指针法遍历文件序列arr，通过移动指针来找到能转储的最大连续文件大小之和；
  2. 将当前文件大小加到curr上；
  3. 如果curr小于等于M，更新ret为curr和ret中的较大值，右指针r向右移动一位；
  4. 如果curr大于M，说明当前连续文件大小之和超过了SATA盘容量，需要调整边界来找到新的连续文件；
  5. 输出能转储的最大连续文件大小之和ret；

五、Java算法源码

public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 每块SATA盘容量int M = Integer.valueOf(sc.nextLine());// 区块链文件大小序列int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();// 序列arr的长度int n = arr.length;// 连续文件的左边界int l = 0;// 连续文件的右边界int r = 0;// 当前连续文件大小之和int curr = 0;// 能转储的最大连续文件大小之和int ret = 0;// 1、使用双指针法遍历文件序列arr，通过移动指针来找到能转储的最大连续文件大小之和。while (r < n) {// 2、将当前文件大小加到curr上curr += arr[r];// 3、如果curr小于等于M，更新ret为curr和ret中的较大值，右指针r向右移动一位if (curr <= M) {ret = Math.max(ret, curr);r ++;// 4、如果curr大于M，说明当前连续文件大小之和超过了SATA盘容量，需要调整边界来找到新的连续文件。} else {// 4.1 将右指针r指向的文件大小从curr中减去curr -= arr[r];// 4.2 将左指针l指向的文件大小从curr中减去curr -= arr[l];// 4.3 左指针l向右移动一位l ++;}}// 5、输出能转储的最大连续文件大小之和retSystem.out.println(ret);}

六、效果展示

1、输入

1000
100 300 500 400 400 150 100

2、输出

950

3、说明

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

下一篇：华为OD机试真题 Java 实现【获得完美走位】【2023Q1 100分】

本文收录于，华为OD机试（JAVA）（2022&2023）

本专栏包含了最新最全的2023年华为OD机试真题，有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新，每天在线答疑。