Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li(1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the "kerf", the extra length lost to sawdust when a sawcut is made; you should ignore it, too.
FJ sadly realizes that he doesn't own a saw with which to cut the wood, so he mosies over to Farmer Don's Farm with this long board and politely asks if he may borrow a saw.
Farmer Don, a closet capitalist, doesn't lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.
Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.
POJ 3253这道题的大意是有一个农夫要把一个木板砍成几块给定长度的小木板，每次据都要收取一定费用，这个费用就是据的这个木版的长度，用赫夫曼树的思路，用优先队列实现。逆向思维，每次都把木板拼接，要想每次都花费最少就得取最小的两个木板拼接起来再把拼接好的木板入队。 http://beeder.github.io/2014/11/25/poj-problem-3253-fence-repair/
这其实就是哈弗曼树的问题。我们可以想象所有小棍子都锯好了，我们要把他们拼接成原来的长木棍，则每拼接一次的长度就是上一次锯的时候剩余的木棍长度，要使剩余长度之和最小，我们可以每次取最短的两根木棍拼接，这样得到的剩余木棍长度之和自然是最小的。而这就是哈弗曼树。
每次取剩余元素中最小的两个求和，把这两个元素删除，然后插入这个和，如此循环直到最后只剩下一个元素。每次都要取最小的两个元素
- public class Main {
- PriorityQueue<Long> qq = new PriorityQueue<Long>(20000);
- void run() {
- Scanner scan = new Scanner(System.in);
- long sum = 0, x, y, temp;
- int n = scan.nextInt();
- for (int i = 0; i < n; i++)
- qq.add(scan.nextLong());
- for (int i = 1; i < n; i++) {
- x = qq.poll();
- y = qq.poll();
- temp = x + y;
- sum += temp;
- qq.add(temp);
- }
- System.out.println(sum);
- }
- public static void main(String[] args) {
- new Main().run();
- }
- }
