PTA修理牧场
发布时间
阅读量：
阅读量
PTA修理牧场
题目：
农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数L
i
个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是L
i
的总和。
但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
输入格式:
输入首先给出正整数N（≤10
4
），表示要将木头锯成N块。第二行给出N个正整数（≤50），表示每段木块的长度。
输出格式:
输出一个整数，即将木头锯成N块的最少花费。
输入样例:
8
4 5 1 2 1 3 1 1
输出样例:
49
思路概括：
使用贪心算法求哈夫曼树，可以使得总权值最小。我们目的是使得花费的钱数最少，正好符合哈夫曼编码；初始的各个长度为给出的最后每段长度，我们实行逆过程，把小段合成一个整体。每次选取两个长度最小的木头进行合并，合并后的木头长度为这两个木头长度之和，消耗的钱数为这两个最小木头的长度和，再将合并后的木头加进队列，依次执行，直到只剩下一个木头。求最小木头可以在整个过程中维护一个优先队列，每次出队的即为长度最小的木头.
代码如下：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
static class Reader {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokenizer = new StringTokenizer("");
static String nextLine() throws IOException{// 读取下一行字符串
return reader.readLine();
}
static String next() throws IOException {// 读取下一个字符串
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {// 读取下一个int型数值
return Integer.parseInt(next());
}
static double nextDouble() throws IOException {// 读取下一个double型数值
return Double.parseDouble(next());
}
}
public static void main(String[] args) throws IOException {
// TODO 自动生成的方法存根
int n=Reader.nextInt();
int ans=0;
PriorityQueue<Integer> que=new PriorityQueue<>();
for(int i=0;i<n;i++)
que.add(Reader.nextInt());
while(que.size()!=1) {
int x=que.poll();
int y=que.poll();
ans+=x+y;
// System.out.println(x+" "+y);
que.add(x+y);
}
System.out.println(ans);
}
}全部评论 (0)
还没有任何评论哟~