55-围栏修复--PriorityQueue java优先队列的应用 java

围栏修复描述
农夫约翰想修修牧场周围的一小部分篱笆。他测量围栏并认定他需要?（1≤ ? ≤20000）厚木板，每一个都具有一些整数长度大号我（1≤ 大号我 ≤50000）单元。然后，他购买了一块足够长的单板长板，以便看到N板（即长度为长度L i的总和）。FJ忽略了“切口”，当切割锯切时，木屑损失了额外的长度; 你也应该忽略它。
FJ遗憾地意识到他没有用锯切割木头的锯子，所以他用这个长板子偷偷地去农民唐的农场，礼貌地问他是否可以借锯。
壁橱资本家Farmer Don并没有给FJ借一块锯，而是向农民John提供了每块N -1切割的费用。切割一块木头的费用与其长度完全相同。切割长度为21的木板需要21美分。
农民唐然后让农夫约翰决定切割木板的顺序和位置。帮助Farmer John确定他可以用来创建N个木板的最低金额。FJ知道他可以以各种不同的顺序切割板，这将导致不同的费用，因为所得到的中间板具有不同的长度。
输入
第1行：一个整数N，木板的数量
第2行.N +1：每行包含一个描述所需木板长度的整数产量
第1行：一个整数：他必须花费N -1削减的最低金额样本输入

3 8 5 8

【55-围栏修复--PriorityQueue java优先队列的应用】样本输出

34

暗示
他希望将长度为21的板切成8,5和8的长度。
原板的尺寸为8 + 5 + 8 = 21。第一次切割将花费21，并且应该用于将板切割成13和8的碎片。第二次切割将花费13，并且应该用于将13切割成8和5.这将花费21 + 13 = 34 。如果将21切割成16和5，则第二次切割将花费16，总共37（超过34）。思路：贪心+优先队列：每次去最小的合并，合并的即为要切的长度，所以每次取最小的两个，然后弹出，并加和放入优先队列。 java中的优先队列： PriorityQueue code:

package lq2018_gs; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; public class test { public static void main(String[] args) { // TODO Auto-generated method stub Queue que = new PriorityQueue(); System.out.println(que.toString()); que.add(20); que.add(10); que.add(-2); que.add(100); System.out.println(que.toString()); while(!que.isEmpty()) { int x = que.peek(); que.poll(); System.out.println("x: " + x); } }}

本题代码：注意要改为 Main 并去掉报名，否则包error time

package lan_qiao; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; public class t1 { public static Queue que = new PriorityQueue(); public static void main(String[] args) { // TODO Auto-generated method stub Scanner cin = new Scanner(System.in); int n = cin.nextInt(); for(int i = 0; i < n; i++) { que.add(cin.nextInt()); } long ans = 0; while(que.size() > 1) { int x = que.poll(); int y = que.poll(); ans += x + y; que.add(x + y); } System.out.println(ans); cin.close(); }}

转载于:https://www.cnblogs.com/zhumengdexiaobai/p/10878063.html