POJ3253 Fence Repair 小顶堆+贪心 - c++编程基础

给了你N个木棒，求把他们组装成一根需要的最小花费，每次只能选两根组装在一起，需要的花费为两个木棒之和，

以前遇到过把一整根切开的，那个是DP，这个则有些类似，可是大胆的猜测了一下，直接每次选取所有木棒中最短的两根，这样就可以了，那么贪心是适用的，但是数量很多，而且两根最短的组装好了得插回去，这样不可能每次都排序吧，

这题首先优先队列肯定是可以做的，

最小堆也是可以的，每次都选出堆里的最小的两个求和再放回去即可

队列本身也就是堆吧，所以差别不大，但是没用过最小堆最大堆的所以用一次把

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                   > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; LL len[20000 + 5];//小顶堆里的元素，注意len[0]代表小顶堆的元素数目 void clear() { memset(len,0,sizeof(len)); } /****构建小顶堆****/ void heap(int i) { int l = i * 2; int r = i * 2 + 1; int minn = i; if(l <= len[0] && len[l] < len[minn]) minn = l; if(r <= len[0] && len[r] < len[minn]) minn = r; if(i != minn) { int tmp = len[i]; len[i] = len[minn]; len[minn] = tmp; heap(minn); } } /******插入小顶堆*****/ void insertheap(LL x) { len[++len[0]] = x; LL tmp = len[0]; while(tmp > 1 && len[tmp] < len[tmp/2]) { int t = len[tmp]; len[tmp] = len[tmp/2]; len[tmp/2] = t; tmp >>= 1; } } LL get() { LL ans1 = len[1]; len[1] = len[len[0]];//拿走第一个以后，把堆尾的拿到堆首 len[0]--; heap(1);//重新排序 LL ans2 = len[1]; len[1] = len[len[0]]; len[0]--; heap(1); insertheap(ans1 + ans2);//取出第一小第二小的，然后相加以后再插回小顶堆 return ans1 + ans2; } int main() { int n; while(scanf("%d",&n) == 1) { clear(); for(int i=1;i<=n;i++) { scanf("%I64d",&len[i]); insertheap(len[i]); } LL ans = 0; for(int i=1;i