首页 > 代码库 > 程序存储问题
程序存储问题
程序存储问题
题目:设有 n 个程序 { 1 , 2 , 3 , … , n } 要存放在长度为 L 的磁带上。程序i存放在磁带上的长度是 li , 1 ≤ i ≤ n 。要求确定这 n 个程序在磁带上的一个存储方案,使得能够在磁带上存储尽可能多的程序。
输入数据中,第一行是 2 个正整数,分别表示程序文件个数和磁带长度L。接下来的 1 行中,有 n 个正整数,表示程序存放在磁带上的长度。
输出为最多可以存储的程序个数。
输入数据示例
6 50
2 3 13 8 80 20
输出数据
5
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); int l = scanner.nextInt(); int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } sort(nums, 0, n - 1);// 排序 int count = 0, sum = 0; for (int i = 0; i < n; i++) { sum += nums[i]; if (sum > l) { break; } else { count++; } } System.out.println(count); } scanner.close(); } // 快排 private static void sort(int[] nums, int start, int end) { if (start >= end) { return; } int key = nums[start]; int i = start + 1; int j = end; while (true) { while (i <= end && nums[i] < key) { i++; } while (j > start && nums[j] > key) { j--; } if (i < j) { swap(nums, i, j); } else { break; } } // 交换j和分界点的值 swap(nums, start, j); // 递归 sort(nums, start, j - 1); sort(nums, j + 1, end); } // 数据交换 private static void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。