題目
有若干個文件，使用刻錄光盤的方式進行備份，假設每張光盤的容量是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);PriorityQueue<Integer> 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），查看當前專欄更新的所有題目。
