赞
踩
区块链底层存储是一个链式文件系统,由顺序的N个文件组成,每个文件的大小不一,依次为F1,F2…Fn。
随着时间的推移,所占存储会越来越大。
云平台考虑将区块链按文件转储到廉价的SATA盘,只有连续的区块链文件才能转储到SATA盘上,且转储的文件之和不能超过SATA盘的容量。
假设每块SATA盘容量为M,求能转储的最大连续文件大小之和。
第一行为SATA盘容量M,1000<=M<=1000000
第二行为区块链文件大小序列F1,F2…Fn。其中 1<=n<=100000, 1<=Fi<=500
求能转储的最大连续文件大小之和
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、输出能转储的最大连续文件大小之和ret System.out.println(ret); }
1000
100 300 500 400 400 150 100
950
最大序列和为950,序列为[400,400,150]。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。