本文地址：

题目名称：Fence Repair

链接：

题意：农夫准备把木板切成n块，每块长度为Li，每次切木板时需要花费切时木板的长度的开销(比如把21切成13和8，开销就是切之前的长度12)。计算把木板切完的最小开销。

思路：直接拿刀去切木板貌似没有什么贪心的思路呀。但是我们把切的过程画成树的样子就会发现开销等于各叶子节点的 木板长度乘以节点深度 的和。反过来想，最短与次短的两块应该在最下面且是兄弟节点，就是每次把最小的两块合起来，然后依次贪心就能得到最小值。(也就是哈夫曼树)

代码如下：

1、直接循环查找最小和次小 O(n2)

1 #include
      
        2 #include
       
         3 using namespace std; 4 typedef long long ll; 5 int L[20005]; 6 int main(){ 7     int n; 8     scanf("%d",&n); 9     for(int i = 0; i < n; i++)10         scanf("%d", &L[i]);11     ll sum = 0;12     while(n > 1){13         int min1 = 0, min2 = 1; //最小和次小14         if(L[min1] > L[min2])15             swap(min1, min2);16         for(int i = 2; i < n; i++){17             if(L[i] < L[min1]){18                 min2 = min1;19                 min1 = i;20             }21             else if(L[i] < L[min2])22                 min2 = i;23         }24         int t = L[min1] + L[min2];25         sum += t;26         if(min1 == n-1) swap(min1,min2);27         L[min1] = t;28         L[min2] = L[n-1];29         n--;30     }31     printf("%lld\n",sum);32     return 0;33 }
       
      

2、用优先队列 O(nlogn)

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 typedef long long LL; 6 int main() { 7     int n; 8     scanf("%d", &n); 9     priority_queue
         

,greater

> que;10 int s;11 for(int i = 0; i < n; i++) {12 scanf("%d", &s);13 que.push(s);14 }15 LL ans = 0;16 while(que.size() > 1) {17 int s1,s2;18 s1 = que.top();19 que.pop();20 s2 = que.top();21 que.pop();22 ans += s1 + s2;23 que.push(s1 + s2);24 }25 printf("%lld\n", ans);26 return 0;27 }