本文共 1780 字，大约阅读时间需要 5 分钟。

题述

农夫约翰为了修理栅栏，要将一块很长的模板切割成N块。准备切成的模板的长度为L1、L2、L3、…、LN，未切割前木板的长度恰好为切割后木板长度的总和。每次切断木板时，需要的开销为这块木板的长度。例如长度为21的木板要切成长度为5、8、8的三块木板。长度为21的木板切成长为13和8的板时，开销为21.再将长度为13的木板切成长度为5和8的板时，开销是13.于是合计开销为34.请求出按照目标要求将木板切割完最小的开销是多少？ 限制条件 1<=N<=20000 0<=Li<=50000 题记 这样的切割方法其实类似于二叉树 这里的每一个叶子结点就对应了切割出的一块块木板。叶子结点的深度就对应了为了得到对应木板所需的切割次数，开销的合计就是各叶子的结点木板长度*结点的深度的总和。这道题其实就是最优二叉树(赫夫曼树)的变形。每次选出权重最小的两个结点，权重相加作为新的结点，以此类推构造出来的二叉树就是最优树。 遇到的问题 最后合并的时候，原来的最小和次小结点(min1和min2)已经没用了，我们需要把新的结点(两个木板的长度)加进去，我们采用从后往前缩小，我们假定让L[min1]存储新结点，L[min2]存储最后一个节点L[N-1]，这里有各种特殊情况：万一min2的值等于N-1，那么这个结点就被我们自动隐藏了，所以需要把min1和min2换一下，这样万一min2等于N-1呢？其实正好，因为min2指向的结点是之后用不上的，所以L[N-1]被隐藏掉也没事。 朴素的方法代码如下

#include 
   
    //修理栅栏using namespace std;const int Maxn=20005;typedef long long ll;//输入int N,L[Maxn];void solve(){
       ll ans=0;    while(N>1){
       //求出最短的板min1和次短板min2    int min1=0,min2=1;    if(L[min1]>L[min2])        swap(min1,min2);    for(int i=2;i
   

使用优先队列解决

优先队列知识补充 priority_queue< Type,Container,Functional> Type就是数据的类型，Container就是容器类型(Container必须是用数组实现的容器，比如vector,deque等等不能用list,STL默认用vector)，Functional就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本类型时，只需要第一个就行了

//升序队列priority_queue
   
    
     ,greater
     
      > que_greater;//降序队列priority_queue
      
       
        ,less
        
         > que_less;
        
       
      
     
    
   

具体代码如下

#include 
   
    #include 
    
     //栅栏修补队列解决方法using namespace std;typedef long long ll;const int Maxn=20005;//输入int N,L[Maxn];void solve(){
       ll ans=0;    //升序队列    priority_queue
     
      
       ,greater
       
        > que;    for(int i=0;i
        
         1){ //取出最短的木板和次短的木板 int min1,min2; min1=que.top(); que.pop(); min2=que.top(); que.pop(); //把两个木板合并加到原来的队列里 ans+=min1+min2; que.push(min1+min2); } printf("%lld\n",ans);}int main(){ scanf("%d",&N); for(int i=0;i
        
       
      
     
    
   

转载地址：http://gyzzi.baihongyu.com/