设计网站的一般过程,网络营销的理论有哪些,wordpress 排行榜 页面,生鲜网站建设费用题目 有若干个文件#xff0c;使用刻录光盘的方式进行备份#xff0c;假设每张光盘的容量是500MB.求使用光盘最少的文件分布方式。所有文件的大小都是整数MB#xff0c;且不超过500MB:文件不能分割、分卷打包 输入描述: 一组文件大小的数据 输出描述: 使用光盘的数量 补充说…题目 有若干个文件使用刻录光盘的方式进行备份假设每张光盘的容量是500MB.求使用光盘最少的文件分布方式。所有文件的大小都是整数MB且不超过500MB:文件不能分割、分卷打包 输入描述: 一组文件大小的数据 输出描述: 使用光盘的数量 补充说明: 不用考虑输入数据不合法的情况:假设最多100个输入文件。 示例1 输入: 100,500,300,200,400 输出: 3 说明: (100,400),(200,300),(500) 3张光盘即可输入和输出内容都不含空格。 示例2 输入: 100,100,200,300 输出: 2 思路 以500 400 300 80 70 70 50 30为例已将nums倒序排列 备份第一个文件500需要第一个光盘 备份第二个文件400需要第二个光盘还剩100空间 备份第三个文件300上次只剩100空间所以得另开第三个光盘备份后还剩200空间 备份第四个文件80此时第二和第三个光盘的剩余空间都能放下到底该放入哪一个呢 假设放入剩余空间较小的那一个 备份第四个文件80放入第二个光盘此时剩余空间20 备份第五个文件70放入第三个光盘剩余空间130 备份第六个文件70放入第三个光盘剩余空间60 备份第七个文件50放入第三个光盘剩余空间10 备份第八个文件30第二个光盘剩余了20的空间第三个光盘剩余了10空间均放不下所以另起第四个光盘。 在此分支得到答案为4假设放入剩余空间较大的那一个 备份第四个文件80放入第三个光盘此时剩余空间120 备份第五个文件70放入第三个光盘剩余空间60 备份第六个文件70放入第二个光盘剩余空间30 备份第七个文件50放入第三个光盘剩余空间10 备份第八个文件30放入第二个光盘剩余空间0 在此分支得到答案为3 很明显从此用例的结果来看放入剩余空间较大的那一个可以更节省光盘。 从逻辑上来分析当两个空间都能放下当前文件时放入更大的空间能够保证放入后两个最小剩余空间更大。比如上面的案例中当前文件为80两个光盘的剩余空间分别为100和200如果放入100那么两个剩余空间变为20和200最小值为20如果放入200那么两个剩余空间为100,120最小值为100此时再备份新的文件时如果其大小超过了20就只能备份到200的空间去那么第一种方案那20的剩余空间就要被浪费掉了。 因此最小剩余空间越大才最省空间。 综上在代码实现时应该用一种结构保证始终能找到剩余空间较大的那一个而剩余空间500-已使用空间。要想剩余空间最大就是使用空间最小可以考虑用最小堆来实现。 如果堆为空或者当前值nums[i]最大剩余空间500说明得另开一个光盘将nums[i]放入最小堆此时堆大小1代表新开了光盘如果nums[i]最大剩余空间500当前文件可以拷贝到上一个光盘那么直接把上一个光盘取出来加上当前文件大小再存回堆中这样堆的size并没有变化也就是没有新开光盘最后返回堆的大小就代表最少光盘数量。 题解
package hwod;import java.util.*;public class DataCopy {public static void main(String[] args) {Scanner sc new Scanner(System.in);int[] nums Arrays.stream(sc.nextLine().split(,)).mapToInt(Integer::parseInt).toArray();System.out.println(dataCopy(nums));}private static int dataCopy(int[] nums) {Arrays.sort(nums);PriorityQueueInteger queue new PriorityQueue();for (int i nums.length-1; i 0; i--) {if (queue.isEmpty() || nums[i] queue.peek() 500) {queue.offer(nums[i]);} else {queue.offer(queue.poll() nums[i]);}}return queue.size();}}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
