poj 3253 Fence Repair (水哈夫曼树)

题目链接：

题目大意：

　　有一根木棍，需要截成n节，每节都有固定的长度，一根长度为x的木棒结成两段，需要花费为x，问截成需要的状态需要最小的花费？

解题思路：

　　哈夫曼数，把每节需要的木棒长度看做树上的节点，把截木棍的过程倒过来，变成把n截木棍接起来，这两个过程的花费是一样的。根据哈夫曼的性质，可知先把最短的两个木棍连起来后，放到剩下的n-2根木棍中，再选取两个最短的连接起来，再放回去，直到全部的木根都连在一起就ok了。

代码：

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <iostream>

 #include <cmath>

 #include <queue>

 using namespace std;

 int main ()

 {

     priority_queue <int> Q;//优先队列，默认大的先出队，所以我们把进队的数取负

     int n;

     long long sum, num, m;

     scanf ("%d", &n);

     while (n --)

     {

         scanf ("%d", &m);

         Q.push(-m);//进队

     }

     sum = ;

     while (Q.size() > )//队列里面的元素个数要大于1

     {

         num = ;

         num += Q.top();//出队两个最短木棍

         Q.pop();

         num += Q.top();

         Q.pop();

         sum += num;//连接起来

         Q.push(num);//进队

     }

     printf ("%lld\n", -sum);

     return ;

 }

巴特西

poj 3253 Fence Repair (水哈夫曼树)

最新文章

热门文章