描述

牛牛现在在学习计算机，他想通过计算机计算n个数的和。
但是计算机计算数字的和是有花费的，比如计算x，y两个数的和，需要花费秒。
计算机一次只能计算一次，牛牛想知道自己怎么合理安排计算的顺序，可以使得花费的时间最短。

输出计算n个数字和的最小花费的时间。

方法一

思路

• 代码如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示有n个数。
     * @param c int整型 参数c
     * @param a int整型一维数组 ai表示第i个数的大小
     * @return long长整型
     */
    public long solve (int n, int c, int[] a) {
        // 空，返回0
        if (n == 0){
            return 0;
        }
        // 创建最小堆
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        // 转换
        for(int i = 0;i < n; ++i){
            queue.offer(a[i]);
        }
        long times = 0;
        // 计算
        while(true){
            int x = queue.poll();
            if (queue.isEmpty()){
                break;
            }
            int y = queue.poll();
            int temp = x + y;
            times += c * (temp);
            queue.offer(temp);
        }
        return times;
    }
}

• 时间复杂度：，一层循环；
• 空间复杂度：，使用堆辅助计算。

方法二

思路

*

• 代码如下：

• 时间复杂度：
• 空间复杂度：