AcWing 148. 合并果子
原题链接
简单
作者:
小呆呆
,
2019-11-07 01:09:41
,
所有人可见
,
阅读 1324
算法分析
- 典型的构造哈夫曼树的问题,只需每次找出最小的两个值合并成一个元素,该做法消耗体力总和最低
时间复杂度 $O(nlogn)$
Java 代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
Queue<Integer> minheap = new PriorityQueue<Integer>();
int n = scan.nextInt();
for(int i = 0;i < n;i++)
{
minheap.add(scan.nextInt());
}
int res = 0;
while(minheap.size() >= 2)
{
int x = minheap.poll();
int y = minheap.poll();
int value = x + y;
res += value;
minheap.add(value);
}
System.out.println(res);
}
}