目录

题目部分

解读与分析

代码实现

题目部分

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

解读与分析

题目解读：

磁盘转存，找出连续的文件，使文件的大小之和不高于转寸磁盘的大小，求最大的文件大小之和。翻译一下，就是：从一组连续的正整数中，找出连续的数字，使连续数字之和不超过指定数字。在符合条件的情况下，连续数字之和最大是多少。

分析与思路：

此题与《华为OD机考算法题：补种未成活胡杨》类似，都是以 0 为左边界，找到一个右边界，使左边界和右边界之间的所有数字符合其条件，然后依次向右移动左边界、右边界，找到下一个符合条件的连续块，逐一比较每个连续块的情况，最终输出符合条件连续块中最优（最优的条件取决于题目要求）的那个。

此题的时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

Java代码

import java.util.Scanner;/** * 区块链文件转储系统 ** @since 2023.09.22 * @version 0.1 * @author Frank * */public class StorageTransfer {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();int limit = Integer.parseInt(input);input = sc.nextLine();String[] strNumbers = input.split(" ");processStorageTransfer(limit, strNumbers);}}private static void processStorageTransfer(int limit, String strNumbers[]) {int[] numbers = new int[ strNumbers.length ];for( int i = 0; i < strNumbers.length; i ++ ){numbers[i] = Integer.parseInt( strNumbers[i] );}int left = 0;int right = 1;int tmpMax = numbers[0];int maxSize = 0;while( right <= numbers.length ){while( ( right < numbers.length ) && ( tmpMax + numbers[right]  maxSize ){maxSize = tmpMax;}if( maxSize == limit ){System.out.println( maxSize );return;}if( right >= numbers.length ){break;}do {tmpMax -= numbers[left];left ++;}while( left  limit);}System.out.println( maxSize );}}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });var iter = rl[Symbol.asyncIterator]();const readline = async () => (await iter.next()).value;void async function() {while (line = await readline()) {var limit = parseInt(line);line = await readline();var strNumbers = line.split(" ");processStorageTransfer(limit, strNumbers);}}();function processStorageTransfer(limit, strNumbers) {var numbers = new Array();for (var i = 0; i < strNumbers.length; i++) {numbers[i] = parseInt(strNumbers[i]);}var left = 0;var right = 1;var tmpMax = numbers[0];var maxSize = 0;while (right <= numbers.length) {while ((right < numbers.length) && (tmpMax + numbers[right]  maxSize) {maxSize = tmpMax;}if (maxSize == limit) {console.log(maxSize);return;}if (right >= numbers.length) {break;}do {tmpMax -= numbers[left];left++;} while (left  limit);}console.log(maxSize);}

(完)