牛牛算数

class Solution {
public:
    /**
     * 返回一个数字表示输出计算n个数字和的最小花费的时间。
     * @param n int整型 表示有n个数。
     * @param c int整型 参数c
     * @param a int整型vector ai表示第i个数的大小
     * @return long长整型
     */
    long long solve(int n, int c, vector<int>& a) {
        long long s = 0, x, y;
        priority_queue<long long, vector<long long>, greater<long long>> q;
        for(int i=0;i<a.size();i++)
            q.push(a[i]);
        for(int i=1;i<a.size();i++){
            x = q.top();
            q.pop();
            y = q.top();
            q.pop();
            s += x+y;
            q.push(x+y);
        }
        return s*c;
    }
};

// 有时候 掌握一个优秀的数据结构也是很重要的
    public long solve (int n, int c, int[] a) {
        // write code here
        PriorityQueue<Integer> heap = new PriorityQueue<>(); // 小顶堆
        
        for(int i = 0; i < a.length; i++) {
            heap.offer(a[i]);
        }
        
        long cost = 0;
        
        while(heap.size() > 1) {
            int num1 = heap.poll();
            int num2 = heap.poll();
            int temp = num1 + num2;
            cost += c*num1 + c*num2;
            heap.offer(temp);
        }
        
        return cost;
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示有n个数。
     * @param c int整型 参数c
     * @param a int整型一维数组 ai表示第i个数的大小
     * @return long长整型
     */
    int index;
    public long solve (int n, int c, int[] a) {
        //优先队列+比较器
        int pre = 0;
        int cur = 0;
        long sum = 0;
        index = 0;
        int heap[] = new int[n];
        for(int i = 0; i < a.length; i++) {
            heapInsert(heap, a[i]);
        }
        while(index > 0) {
            if(index == 1) {//不包含
                return sum * c;
            }
            pre = heap[0];
            heaplify(heap);
            cur = heap[0];
            heaplify(heap);
            sum += pre + cur;
            heapInsert(heap, pre + cur);
        }
        return sum;//走不到
    }
    public void heapInsert(int[] heap, int value) {
        int cur = index;
        heap[index++] = value;
        while(cur > 0) {
            int parent = (cur - 1)/2;
            if(heap[parent] > heap[cur] ) {
                int temp = heap[parent];
                heap[parent] = heap[cur];
                heap[cur] = temp;
                cur = parent;
            }else {
                break;
            }
        }
    }
    public void heaplify(int[] heap) {
        index--;
        heap[0] = heap[index];
        int cur = 0;
        while(cur < index) {
            int leftChild = cur * 2 + 1;
            int rightChild = cur * 2 + 2;
            int smallest = cur;
            if(leftChild < index && heap[leftChild] < heap[cur]) {
                smallest = leftChild;
            }
            if(rightChild < index && heap[rightChild] < heap[smallest]) {
                smallest = rightChild;
            }
            if(smallest == cur) {
                break;
            }else {
                int temp = heap[smallest];
                heap[smallest] = heap[cur];
                heap[cur] = temp;
                cur = smallest;
            }
        }
    }
}