数列 Reduction

1. 题意：

给一个数列 eg. [1,2,3]，nums[i]+nums[j] 然后把这个数字放回array，这次操作的cost就是nums[i]+nums[j]，[3,3]。重复步骤，直到array里边只有1个数字。这个步骤要循环n-1次。因为每次数量减1。

求minimum cost 3+6 = 9

2. 算法：

想要最小cost，那么每次选的nums[i] 和 nums[j]应该是这个array里边的最小值。因为如果加了一个值，那么这个值在某个时刻还要再加不知道几遍。因此越小越好。

易错点：先sort array，按照从小数开始加，每次加前一个sum
对于[1,2,2,2,2,3] 而言最小是 [1,2,2,2,2,3]  -> [2,2,2,3,3] ->[2,3,3,4] ->[3,4,5]->[5,7]->[12]
minSum = 3+ 4+5+7+12
如果按照错误算法是[1,2,2,2,2,3]  -> [3,2,2,2,3] -> [5,2,2,3]->[7,2,3]->[9,3]->[12]
minSum = 3+5+7+9+12

 public int reductionCost(int[] nums){  
   if(nums.length <= 1) return 0;  
   int sum = 0;  
   PriorityQueue<Integer> pq = new PriorityQueue<>();  
   for(int num : nums){  
     pq.add(num);  
   }  
   while(pq.size()>1){  
     int x = pq.poll();  
     int y = pq.poll();  
     sum += x+y;  
     pq.offer(x+y);  
   }  
   return sum;  
 }