华为OD机考算法题：区块链文件转储系统-Toy模板网

这篇具有很好参考价值的文章主要介绍了华为OD机考算法题：区块链文件转储系统。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目部分


题目	区块链文件转储系统
难度	难
题目说明	区块链底层存储是一个链式文件系统，由顺序的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] <= limit ) )
			{
				tmpMax += numbers[right]; 
				right ++;
			}
			if( tmpMax > maxSize )
			{
				maxSize = tmpMax;
			}
			if( maxSize == limit )
			{
				System.out.println( maxSize );
				return;
			}
			if( right >= numbers.length )
			{
				break;
			}
			do {
				tmpMax -= numbers[left];
				left ++;
			}while( left < numbers.length &&  tmpMax > 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] <= limit)) {
            tmpMax += numbers[right];
            right++;
        }
        if (tmpMax > maxSize) {
            maxSize = tmpMax;
        }
        if (maxSize == limit) {
            console.log(maxSize);
            return;
        }
        if (right >= numbers.length) {
            break;
        }
        do {
            tmpMax -= numbers[left];
            left++;
        } while (left < numbers.length && tmpMax > limit);

    }

    console.log(maxSize);
}

(完)文章来源地址https://www.toymoban.com/news/detail-714323.html

到了这里，关于华为OD机考算法题：区块链文件转储系统的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！