6、贪心 &哈夫曼树

AcWing 148. 合并果子

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();

    }

    //    构造小顶堆：
    PriorityQueue<Integer> small_heap
            = new PriorityQueue<>();

    void init() {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        for (int i = 0; i < n; i++) {
            small_heap.offer(sc.nextInt());
        }
        int res=0;
        while (small_heap.size()>1){
            int a=small_heap.poll();
            int b=small_heap.poll();
            res+=a+b;
            small_heap.offer(a+b);
        }
        System.out.println(res);
    }
}