题目链接
输入
第一行：木板数
第二行：每块木板的开销
输出
将木板切割完最小的开销是多少
Sample Input
3
8
5
8
Sample Output
34
解题思路
算法1 ： 贪心 O(n^2)
算法2 ： 优先队列 O(nlogn)
我这里用的算法2
为了使花费最小，应该从优先队列中取出最短的两块木板，并且把最短的两块木板之和放入队列中，一共进行了O(n)次的O(logn)的操作，总的时间复杂度就是O(nlogn)，比O(n^2)快很多。
import java.util.PriorityQueue;
import java.util.Scanner;public class Main{public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);PriorityQueue<Integer> que = new PriorityQueue<Integer>();int n = sc.nextInt();for(int i = 0; i < n; i++) {int a = sc.nextInt();que.add(a);}long res = 0; // 怕超while(que.size() > 1) {int q1 = que.poll();int q2 = que.poll();res += q1 + q2;que.add(q1 + q2);}System.out.println(res);}
}