牛牛算数——最小堆解法

为了使得花费最小，就要使越大的数字越晚计算，每次取最小的两个值进行计算。借助最小堆，每次计算最小的两个数，将两个数的和放入最小堆，直至堆的大小为1。

import java.util.*;


public class Solution {
    /**
     * 返回一个数字表示输出计算n个数字和的最小花费的时间。
     * @param n int整型 表示有n个数。
     * @param c int整型 参数c
     * @param a int整型一维数组 ai表示第i个数的大小
     * @return long长整型
     */
    public long solve(int n, int c, int[] a) {
        long res = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i : a)
            pq.offer(i);
        while (pq.size() != 1) {
            int x = pq.poll();
            int y = pq.poll();
            int xy = x + y;
            res += xy;
            pq.offer(xy);
        }
        return c * res;
    }
}