1 3 1 2 9
15
一看就知道是huffman树,刚开始傻乎乎的用数组模拟,WA了好多次,后来一看,恍然大悟——优先队列,然后还有就是这东西要开long类型。。。。要是比赛什么
的真的是被自己坑死,多写点题目吧!
/*模拟哈夫曼树,每次取最小的两个(优先队列模拟)*/ //大坑啊!!!LONG才能过 。。。。因为最大可以达到两亿多 ,(吐槽下,有小明耕田都不需要牛了) import java.util.PriorityQueue; import java.util.Scanner; public class 懒省事的小明 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tcase = sc.nextInt(); while (tcase-- > 0) { PriorityQueue<Long> q = new PriorityQueue<Long>(); int n = sc.nextInt(); long num; for(int i=0;i<n;i++){ num = sc.nextLong(); q.add(num); } long sum=0; while(q.size()!=1){ //留一个防止队列为空抛出异常 NoSuchElementException,而且根不需要加进去了 long x = q.remove(); long y =q.remove(); sum+=(x+y); q.add(x+y); } while(!q.isEmpty()){ q.remove(); } System.out.println(sum); } } }
原文:http://www.cnblogs.com/liyinggang/p/5031287.html