程式存儲問題

程式存儲問題

題目：設有 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;
  }
}