华为OD机考算法题：区块链文件转储系统_华为od 磁盘转存,找出连续的文件,使文件的大小之和不高于转寸磁盘的大小

目录

题目部分

解读与分析

代码实现

---

题目部分

---

解读与分析

题目解读：

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

分析与思路：

此题与《华为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);
}

(完)