题意：
给定n个文件， 和一个list of file size， 求minimum time to merge file
Example1:
Input:
files = {8， 4， 6， 12}
numOfSubFiles = 4
Output:
58
Explaination:
先将 4 和 6 merge为 size 是 10 的新file。目前为止耗时为10。 files 变为 {8， 10， 12}
再将 8 和 10 merge为 size 是 18 的新file。目前为止耗时为 10 + 18 = 28。files 变为 {12， 18}
最后将 12 和 18 merge为 size 是 30 的新file。目前为止耗时为 10 + 18 + 30 = 58。 files 变为 {30}
Example2:
Input:
files = {3, 1, 2}
numOfSubFiles = 3
Output:
9
Explaination:
1 + 2 = 3;
3 + 3 = 6;
3 + 6 = 9
Example3:
Input:
files = {8, 3, 5, 2, 15}
numOfSubFiles = 5
Output:
66
Explaination:
2 + 3 = 5;
5+5 = 10;
10 + 8 = 18;
18 + 15 = 33;
5 + 10 + 18 + 33 = 66
思路： PriorityQueue
将files中所有元素放入minHeap，每次poll两个最小的，merge之后放回minHeap。直至minHeap中只剩一个元素。输出循环中的累计时间。
复杂度：
时间： O(nlogn)
空间： O(n)
代码
1 public class MergeFilesByPairs { 2 public int mergeFiles(int numOfSubFiles, List<Integer> files) { 3 int resSum = 0; 4 PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2); 5 for (int i = 0; i < files.size(); i++) { 6 minHeap.add(files.get(i)); 7 } 8 while (minHeap.size() != 1) { 9 int a = minHeap.poll(); 10 int b = minHeap.poll(); 11 int temSum = a + b; 12 resSum += temSum; 13 minHeap.add(temSum); 14 } 15 return resSum; 16 } 17 18 public static void main(String[] args) { 19 MergeFilesByPairs test = new MergeFilesByPairs(); 20 // TEST CASE1: files = {8， 4， 6， 12} 21 int numOfSubFiles = 4; 22 List<Integer> list = new ArrayList<>(); 23 list.add(8); 24 list.add(4); 25 list.add(6); 26 list.add(12); 27 System.out.println("TEST CASE1:"); 28 System.out.println(test.mergeFiles(numOfSubFiles, list)); 29 30 // TEST CASE2: files = {3, 1, 2} 31 int n2 = 3; 32 List<Integer> l2 = new ArrayList<>(); 33 l2.add(3); 34 l2.add(1); 35 l2.add(2); 36 System.out.println("TEST CASE2:"); 37 System.out.println(test.mergeFiles(n2, l2)); 38 39 // TEST CASE3: files = {8, 3, 5, 2, 15} 40 int n3 = 5; 41 List<Integer> l3 = new ArrayList<>(); 42 l3.add(8); 43 l3.add(3); 44 l3.add(5); 45 l3.add(2); 46 l3.add(15); 47 System.out.println("TEST CASE3:"); 48 System.out.println(test.mergeFiles(n3, l3)); 49 } 50 }
参考：
https://www.geeksforgeeks.org/optimal-file-merge-patterns/
https://leetcode.com/problems/minimum-cost-to-merge-stones/description/
https://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/
转载于:https://www.cnblogs.com/liuliu5151/p/11026117.html
